Questions tagged [nearest-neighbour]
The point from the dataset that is closest to the query point.
79 questions
2
votes
0
answers
28
views
Resumable approximate k-nearest-neighbor search
I'm using keypoint-based comparison techniques to find duplicate images from a (potentially very large) collection of images. My basic algorithm is to extract keypoints from each image, and for each ...
- 1,025
0
votes
0
answers
39
views
False positive rate of distance-sensitive bloom filter
Update: I thought about this more and if I understand correctly
All = (volume of D-dimensional hypersphere of radius 1) = $\frac {\pi^{(\frac D2)}} {(\frac D2)!}$
Ground-truth positive = (volume of D-...
1
vote
1
answer
75
views
Lower bound for exact nearest neighbor search for fixed dimensionality
Suppose we are given a finite set $\mathcal{X}\in\mathbb{R}^{n\times d}$ of $n$ unique points in $\mathbb{R}^d$ and a metric $m$. The task is, for each $x\in\mathcal{X}$, compute the nearest neigbor ...
- 226
1
vote
2
answers
103
views
O(N log N) algorithm/implementation for maximum inner product search
I am in a situation where I have a query space Q and a key space K, both filled with N d-dimensional real vectors (N ≈ 10^6, d ≈ 50). For each query q, I want to find the k≈10 keys k_i that have the ...
2
votes
1
answer
180
views
Kd-trees excluding some splitting dimensions
I have a 12-dimensional state-space and would like to use a kd-tree to partition my data, so that nearest neighbour operations can be performed quickly. Unfortunately I have the issue that three of ...
- 143
2
votes
1
answer
151
views
Optimal graph data structure for set of points that allows dynamic updates
We aim to optimize the execution of a specific task.
Consider a set, P, containing N 2D points. A new query point, p1, is introduced, and the objective is to identify the nearest point in P to p1. If ...
- 31
1
vote
0
answers
49
views
Matching a 2D points cloud to polylines
I have a (2D) point cloud of reasonable size (say some thousands of points) and a set of (2D) polylines also of a reasonable size. I want to assess the discrepancies between the two geometries and for ...
user16034
2
votes
1
answer
141
views
Space efficient data structure to store precomputed All Nearest Neighbors in high dimensions
Seeking an indexing data structure that is smaller than quadratic in space.
As part of an NLP algorithm using word embeddings of 300-dimensions, I am trying to improve the speed of Word Mover's ...
- 261
0
votes
1
answer
109
views
Finding pixel closest (grid points) to rectilinear polygons
I have rectilinear polygons present, and they are surrounded by grids(grey rectangle with dots denoting center) as shown in the diagram below. There are some areas where grids are not present - like ...
- 3
0
votes
1
answer
372
views
Finding the best algorithm for nearest neighbor search in a 2D plane with moving points
I am looking for an efficient way to perform nearest neighbor searches within a specified radius in a two-dimensional plane. According to Wikipedia, space-partitioning data structures, such as :
k-d ...
- 295
0
votes
0
answers
49
views
How to show that Nearest Neighbour be parallelable?
I am currently reading nearest Neighbour search problem where given a set of points, preprocess it so that given a query point one can find a nearest neighbor.
There are two phases, preprocessing ...
- 1
1
vote
1
answer
349
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 ...
- 187
4
votes
3
answers
626
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 ...
user16034
2
votes
0
answers
183
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
1
vote
0
answers
41
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 ...
