Questions tagged [nearest-neighbour]

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

23 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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. ...
user avatar
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?)...
user avatar
  • 141
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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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&...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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-...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 61
1 vote
0 answers
18 views

Finding fewest strings that cover $\Sigma^n$ up to $R$ edit operations

Let $\Sigma$ be the alphabet, $0<R<n$ be an integer and let $\Sigma^n$ denote the set of all strings of length $n$ over the alphabet. The task is to find the minimum $m$ such that there exist ...
user avatar
0 votes
0 answers
28 views

Data structure for incremental KNN (IKNN) search over high-dimensional vectors

I have a database $D$ of n-dimensional numerical vectors, and I want to do an incremental KNN (IKNN) search over the vectors in $D$. More precisely, given a query vector $v_q \in D$ I need to find $k$ ...
user avatar
0 votes
0 answers
142 views

Is there a best algorithm for Nearest Neighbor Search in Hamming spaces?

I need an algorithm to solve the EXACT Nearest Neighbor problem (I also googled for the keywords "similarity search in binary strings" trying to find better solutions but I couldn't find a ...
user avatar
  • 137
0 votes
0 answers
29 views

Connecting islands to the mainland via flood fill

Say I have a large area filled using floodfill: Where the area in white has been flooded, and all other ares are not connected. I would like to "bridge" these islands to the main area in white, but ...
user avatar
  • 143
0 votes
0 answers
26 views

Finding the closest point in a set in o(n) time

Suppose I have a set S which is a set of points in a 3D plane. Given point P, is it possible to construct a data structure A such that the closest point to P in A can be found in o(n) time? My ...
user avatar
0 votes
1 answer
161 views

Is this computational complexity of the k-NN (custom distance) correct?

I read on a book that in general k-NN (no optimizations), given $d$ dimensions $n$ examples every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, ...
user avatar
0 votes
0 answers
389 views

What is the advantage of product quantization?

I'm reading Product Quantization for Nearest Neighbor Search. Quoting page 4: The strength of a product quantizer is to produce a large set of centroids from several small sets of centroids: ...
user avatar
  • 117
0 votes
0 answers
321 views

Support Vector Machines vs K-Nearest Neighbors

Let's say we have trained a Support Vector Machine with a Gaussian Kernel. When we feed our model an example, it classifies it based on its similarity to landmarks (distance to examples in our ...
user avatar