# Questions tagged [nearest-neighbour]

The point from the dataset that is closest to the query point.

66 questions
Filter by
Sorted by
Tagged with
878 views

### Why Is KD-Tree-based Nearest Neighbor Exponential in K?

I've read in many papers on higher-dimensional nearest neighbor search that KD-Trees are exponential in K, but I can't seem to determine why. What I'm looking for is a solid runtime-complexity ...
674 views

513 views

### Nearest Neighbor Search in Spherical Coordinates

I am familiar with k-d trees being used to find nearest neighbors (NN) in 3-D euclidean space however in my particular case I am given a huge array of spherical coordinates. Due to accuracy ...
138 views

### Cannot find paper: All k nearest neighbors search in N*log(N) using distance indices for log(N) support points

I remember reading a paper about finding k nearest neighbors for all N multi-dimensional objects in the set. I've tries to find it again many times, but have failed so far. The algorithm was as ...
88 views

### What is the best known data structure for online dk-NNG?

I want to build the distance constrained k-Nearest Neighbours Graph, i.e. for every point $p$ in the data cloud $P$ there are at most $k$ undirected edges to points that are closest among all possible ...
31 views

### What is the purpose of standardization in machine learning?

I'm just getting started with learning about K-nearest neighbor and am having a hard time understanding why standardization is required. Reading through, I came across a section saying When ...
173 views

### Data Structure for k Nearest Neighbour Search in D dimension using only point cloud as query points

I have a point cloud of N points in D-dimensional space with periodic boundary conditions, where N can range from 500 to 10^8 and D can range from 1 to 20. The distribution of points varies wildly, ...
516 views

### Why is exact nearest neighbor search hard in high dimensional spaces?

I started research on nearest neighbor search in IR a couple of weeks ago. I am still very new to this field, but what I discovered so far from literature is: 1) For the exact nearest neighbor ...
844 views

### kd-tree stores points in inner nodes? If yes, how to search for NN?

The link in wikipedia about kd-trees store points in the inner nodes. I have to perform NN queries and I think (newbie here), I am understanding the concept. However, I was said to study Kd-trees ...
465 views

### Searching a sorted array to find the $k$ closest values to a target value $T$

Let $A$ be a sorted array of $N$ values. I am interested in finding the index $j$ such that the elements $A_j, A_{j + 1}, ..., A_{j + k - 1}$ have the $k$ closest values to the given target value $T$. ...
420 views

### What is the state of the art for k nearest neighbour search?

I'm not an computer scientist, but still use/have an algorithm to find the $k$ nearest neighbours from a cloud of $N$ points in $d$ (my case $d=3$) dimensional space using some distance measure (in my ...
496 views

### How to find the nearest point in the coordinate system

There are so many points in the coordinate system. When a specific point is given in the coordinate system, I want to find the closest point to the straight line distance. For example, if you have 800 ...
68 views

### A data structure that makes finding close objects easy

I’m working on a project that involves a robot and a very large number of reference points. The robot moves around, while the reference points are fixed in space. I would like the robot to be able to ...
83 views

### How to embed Pearson distance into Euclidean space

I have a lot of numerical vectors, each of dimension 1000. I would like to compare them according to their Pearson distance. This works fine but comparing all vectors to each other is quadratic time ...
43 views

### Nearest neighbour based on subjective human comparison - is this a thing?

I am looking for some clues as to the type of algorithm/data structure or general field of CS to look into... I have a collection of items that I would like to have a human subjectively compare such ...
203 views

### Using k-NN for Exact Match in Hamming Space (after Multi-index Hashing)

Before the Question: Greene, Parnas and Yao presented a scheme which, for binary data chosen uniformily a random, retrieves all points within Hamming distance r of a given point in time $O(d n^{r/d})$...
101 views

### Looking for an efficient algorithm quickly find the nearest line (defined by perpendicular distance) to an arbitrary point

I have a large set of lines in 2D with a known start point and end point, and would like to find the nearest (defined by perpendicular distance) of those edges (or the extension of those edges past ...
2k views

### All nearest neighbor in a changing 2d euclidean space

I am in need of an algorithm for a part of a game (a mod) I am making. I have abstracted the problem: Given a 2D space with $N$ random points $p_1...p_n$, calculate the nearest neighbor of each of ...
43 views

### Nearest line-segment to a query point or conversely

I have a set of line segments (say 1000 of them) and a query point. I want to find the segment which is the closest in the Euclidean sense (if the point does not project on the segment I accept two ...
### Bowyer-Watson Delaunay Triangulation neighbour walk in $O(n^{1/d})$
The Bowyer-Watson Algorithm for creating Delaunay Triangulations works iteratively. Let's say that we have a Delaunay triangulation of $n-1$ points. Now we add the $n$-th point. In order to update the ...