Questions tagged [nearest-neighbour]
The point from the dataset that is closest to the query point.
66
questions
10
votes
1
answer
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 ...
- 200
8
votes
2
answers
674
views
How to efficiently compute the most isolated point?
Given a finite set $S$ of points in $\mathbb R^d$, how can we efficiently compute a "most isolated point" $x\in S$?
We define a "most isolated point" $x$ by
$$x = \arg\max_{p \in S} \min_{q \in S \...
- 363
7
votes
2
answers
3k
views
Find k nearest neighbors on a sphere
Given a set $S$ of $N$ points on a sphere, and another point $P$ on the sphere, I want to find the $k$ points in $S$ that are the closest (Euclidean or great circle distance).
I'm willing to do a ...
- 173
7
votes
2
answers
168
views
A key-value datastructure with fast (on average) member move and nearest neighbors search?
I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N ...
- 201
7
votes
2
answers
990
views
Fast and space efficient data structure for nearest neighbors in 3 dimensions?
I am looking for data structures to answer nearest neighbor queries in 3D which are reasonably space efficient (ie use at most $O(n^{1+\epsilon})$ space) and fast ($O(n^{\epsilon})$ or $O(log^k(n))$ ...
- 171
6
votes
2
answers
2k
views
Finding k-nearest neighbors to a set of nodes in a large graph
Given a large graph $G=(V,E)$, a set of nodes $S\subseteq V$, the problem is finding the $k$-nearest nodes in $V$ to the nodes in $S$.
Given a pair of nodes $(u,v)$, the distance $d(u,v)$ between $u$ ...
- 227
5
votes
1
answer
841
views
n closest points in a set of lat/long coordinates
Here's my problem:
I have a website where people can search based on their location (which is converted to lat/long coordinates). I have many products stored in a database with their lat/long ...
- 205
4
votes
1
answer
147
views
Finding pairs of points that have a given offset
Problem: Given a set of points $S = \{x_1, x_2, x_3, ..., x_n\}$ from $\mathbb{R}^m$ and an offset vector $v \in \mathbb{R}^m$, find a set $Z \subseteq S \times S$ containing $k$ pairs of points $(x_i,...
- 349
4
votes
1
answer
833
views
Find the closest string to a fixed set of strings
I want to find the closest string to a fixed set of strings. The strings are all equal in length, and the number of strings in the set is relatively small (compared to all the possible strings of the ...
- 218
4
votes
1
answer
788
views
Best data structure for high dimensional nearest neighbor search
I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also I'...
- 141
4
votes
0
answers
37
views
Is there a name for the class of distance functions that are compatible with k-d trees?
The typical nearest neighbor search implementation for k-d trees prunes branches when the distance between the target and the pivot along the current axis exceeds the smallest distance found so far. ...
4
votes
0
answers
70
views
Repeated nearest-neighbor queries
If I want to make N repeated (i.e. millions of) 2D nearest-neighbor queries on a pointset of size M, is traveling down into a KD-Tree most efficient or are there better ways to do this? (e.g. Voronoi?)...
- 141
3
votes
2
answers
196
views
Efficient Data Structure for Closest Euclidean Distance
The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628.
A network of ...
- 33
3
votes
2
answers
3k
views
Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?
I just wrote a program that runs the Travelling Salesman Problem using the Nearest Neighbor Algorithm. Afterwards, I started looking into Minimum Spanning Trees (MST).
From my understanding:
The ...
- 235
3
votes
1
answer
9k
views
k-nearest neighbors (Euclidean distance): How to process multiple attributes?
Given this sample:
$$\begin{array}{|c|c|c|} \hline
X1 & X2 (Kg/m^2) & \text{Class} \\ \hline
8 & 4 & A \\ \hline
4 & 5 & B \\ \hline
4 & 6 & B \\ \hline
7 & 7 &...
3
votes
1
answer
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 ...
- 131
3
votes
1
answer
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 ...
- 151
3
votes
1
answer
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 ...
- 9,325
3
votes
0
answers
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 ...
- 131
3
votes
0
answers
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, ...
- 31
3
votes
0
answers
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 ...
- 31
2
votes
1
answer
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 ...
- 251
2
votes
1
answer
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$. ...
- 175
2
votes
1
answer
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 ...
- 121
2
votes
2
answers
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 ...
- 121
2
votes
2
answers
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 ...
- 767
2
votes
1
answer
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 ...
- 829
2
votes
1
answer
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 ...
- 123
2
votes
1
answer
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})$...
- 137
2
votes
2
answers
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 ...
- 23
2
votes
2
answers
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 ...
- 23
2
votes
2
answers
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 ...
- 3,912
2
votes
0
answers
67
views
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 ...
- 21
2
votes
0
answers
23
views
Does there exist a locality sensitive hashing for $\ell_p$-norm distance where $p>2$?
It is well known that the $p$-stable distribution can be used to generate locality sensitive hash code for $\ell_p$-norm distance measure where $p \le 2$. However, it seems that the situation for $p&...
- 258
2
votes
0
answers
17
views
Best asymptotic randomized multidimensional index?
What data structure has the best asymptotic running time for nearest-neighbor search on multidimensional data? I am interested in both preprocessing time and query time, but let's restrict attention ...
- 121
2
votes
0
answers
36
views
Fast searching time for nearest neighbours
I am using KD trees to do nearest neighbour searching. My understanding is that it takes $O(n \log n)$ effort to create the tree where $n$ is the number of points and that it takes $O(m \log n)$ to do ...
- 21
2
votes
0
answers
248
views
How can I improve my KNN classifier?
I'm trying to teach myself a bit about machine learning, so one of the first things I did was implement a KNN classifier in ruby. My goal was to classify text product reviews into 8 classes:
books-...
- 235
2
votes
1
answer
116
views
Find the nearest sum to a given number of two elements in sorted matrix
Given a sorted $n\times n$ matrix $A$ of real values. That is $a_{ki}<a_{kj}$ and $a_{it}<a_{jt}$, when $i<j$. Propose and algorithm, finding two elements of this matrix with the sum nearest ...
1
vote
2
answers
111
views
kdtree or balltree supporting insertion/deletion
I'm looking for a data structure to perform nearest-neighbor searches in 3D Euclidean space. I have used kd- and balltrees for this purpose before, but my problem is more sophisticated this time. I'd ...
- 111
1
vote
1
answer
37
views
A nearest neighbor data structure for meshes
I am trying to find a lightweight data structure to find the nearest neighbor mesh (a mesh being a collection of non-unique triangles) for a given point in R3 (3D Euclidean space). I have seen nearest ...
- 157
1
vote
1
answer
80
views
Find all group of neighbors with a constraint weight
Forgive if this seems like a repeated question. However, I couldn't find a specific algorithm to my needs.
I have nodes that have weights with each other. I want to find all unique groups of nodes, ...
- 155
1
vote
1
answer
18
views
How to give the nearest text that the user has written
In my database I have 1500 food dishes, not all are single words, there are compound words like "cheese with dried fruit and nuts". And I have them in 5 languages (de, en, fr, es, it).
My ...
- 111
1
vote
1
answer
96
views
Nearest neighbor search in latitude/longitude coordinates
I have two sets of lat/long points, $A$ and $B$. For each point $a$ in $A$, I want to find the corresponding closest point (by Haversine distance) $b$ in $B$. I'd like to use a space-partitioning tree,...
- 11
1
vote
1
answer
74
views
Distance to $k$th nearest neighbor efficiently for arbitrary $k$
Problem. Given $X$ a finite metric space of cardinality $n$, construct a data structure in subquadratic time such that the query ...
- 113
1
vote
1
answer
188
views
Algorithm to find what points are the nearest to other points
I have two lists:
Location list, it contains point of interest
People list, it contains coordinates of every person. One single person could be in the list multiple times, depending from the log ...
- 13
1
vote
1
answer
366
views
In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance?
In Chapter 3 of Mining of Massive Datasets, the basis of locality sensitive hashing is explained. They notably mention simhash for the cosine distance, where random hyperplanes are generated, and for ...
- 113
1
vote
1
answer
605
views
Finding the nearest neighbour of an existing 2d point in a set of points within $\mathcal{O}(\log{}n)$ time
Question
Is it possible to find an existing point's nearest neighbour within a logarithmic upper bound?
What I've tried
I have:
the set of points $P$,
a point $p$, where $p\in P$,
a point $q$, ...
- 111
1
vote
0
answers
11
views
What datastructure to query nearest neighbor with constraint on parameters
I have about 200'000 data points distributed on the unit-sphere.
Aside of each point's location on the unit-sphere, it has also assigned a width and height.
I can perform nearest-neighbor queries by ...
1
vote
0
answers
14
views
Batching multiple nearest surface queries: Is it faster? Are there better algorithms?
I'm working on an algorithm that computes lots of "nearest point on a triangulated surface" queries in 3d as a way to resample data sets, and I'm wondering if there is any information out ...
- 11
1
vote
0
answers
27
views
How to cluster N sets into N subsets ,so that we can determine which set a point is from by checking its nearest neighbor in aforementioned subsets?
Question 1:
Given N sets of points $S_1$ ... $S_n$ (no intersection between $S_i$ and $S_j$ when i != j),
I want to find subsets of $S_1$ ... $S_n$ (call them $T_1$ ... $T_n$ respectively)
So that ...
- 61