6 votes
Accepted

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

Without storing points in the inner nodes, but the cut value and cut coordinate, one can use this algorithm to perform NN search: ...
  • 251
4 votes
Accepted

Find k nearest neighbors on a sphere

Use the space partitioning approach to nearest neighbor search. For instance, one approach is to use a $k$-d tree on on the surface of the sphere. You can express every point on the sphere using ...
  • 145k
4 votes
Accepted

Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?

Your algorithm starts at some vertex and then always move to the closest vertex that's not been visited so far. That's not guaranteed to find the minimum spanning tree, as the example in your question ...
4 votes

Finding pairs of points that have a given offset

One optimization I would propose is over the brute force search: $$ \begin{align*} d(\mathbf{x}_i, \mathbf{x}_j) &= \lVert (\mathbf{x}_i-\mathbf{x}_j) - \mathbf{v} \rVert^2\\ &= \sum\limits_{...
3 votes

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

It seems hard to imagine that your claimed running time is correct, for a method that works in an arbitrary number of dimensions. It sounds like you are claiming that your data structures works in an ...
  • 145k
3 votes
Accepted

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

You can do it in two binary searches. For simplicity I assume that all numbers are distinct and, even more, absolute differences between $T$ and all other elements are distinct too. The solution is ...
3 votes
Accepted

k-nearest neighbors (Euclidean distance): How to process multiple attributes?

Straight from definition: $\sqrt{(q_1-p_1)^2 + (q_2-p_2)^2 + \cdots + (q_n-p_n)^2}$ In your particular case $n = 3$, so the query should also be 3D (e.g. {7, 4, 3}. $\sqrt{(q_1-p_1)^2 + (q_2-p_2)^2 ...
  • 9,335
3 votes

A key-value datastructure with fast (on average) member move and nearest neighbors search?

An octree or k-d tree are standard data structures for this sort of task, and should provide reasonably efficient support for all of the operations you listed.
  • 145k
3 votes

Efficient Data Structure for Closest Euclidean Distance

It seems that the relevant data structure might be a dynamic Voronoi diagram. Voronoi diagrams are often the answer when a set of points on the plane is involved. In this case, since the point set ...
3 votes
Accepted

Efficient Data Structure for Closest Euclidean Distance

If I understand this correctly, most spatial indexes could be used. Spatial indexes typically have about $O(log{V})$ insertion time and similar lookup time for nearest neighbors. Of course you can ...
  • 709
2 votes

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

kNN tends to be exponential because the search space increases with $2^k$. Imagine you partition the space around your search point into quadrants. For k=1 you just have to search two 'quadrants' (...
  • 709
2 votes
Accepted

n closest points in a set of lat/long coordinates

Your problem (at least the second variant) is known as 2D range searching. Commonly used data structures are range trees and k-d trees. Searching for range searching on the web will open you a window ...
2 votes

Find k nearest neighbors on a sphere

Here are links to two different software packages that address your question. It may be worth studying each to see if the methods they employ satisfy your needs: (1) Matlab GridSphere. "A geodesic ...
2 votes

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

You don't need sophisticated data structures or algorithms to handle this case. Exact match (r=0) just means that you want to store a set $S$ of points in a way so that, given $x$, you can test ...
  • 145k
2 votes

A key-value datastructure with fast (on average) member move and nearest neighbors search?

The Covertree is a specialized data structure for neighbour search. However I don't know it's update performance. A better option may be the PH-Tree (my own implementation). It is similar to a ...
  • 709
2 votes
Accepted

How to embed Pearson distance into Euclidean space

Yes. Normalize the vectors, then use the Euclidean ($L_2$) distance. In particular, map the vector $v=(v_1,\dots,v_n)$ to the vector $$\tilde{v} = ((v_1-\mu)/s,\dots,(v_n-\mu)/s)$$ where $\mu=(v_1+...
  • 145k
2 votes
Accepted

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

Found the paper finally. Not sure I've read exactly the same paper (maybe I read some SO or SE answer or some other paper that inspired/was inspired by this paper). Nethertheless, the algorithm is ...
  • 151
2 votes
Accepted

Find all group of neighbors with a constraint weight

Your problem is the same as listing all cliques in a graph. Given your weight matrix, construct a graph in which two vertices are connected if the weight between them is below the threshold. A clique ...
2 votes

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

I'm not familiar with dk-NNG, but have you tried a PH-Tree? It has excellent insertion times and very good kNN search. I tested several scenarios with up to 40 dimension and $10^6$ and $10^7$ points. ...
  • 709
2 votes
Accepted

Counting arrays with Euclidean distance at most 2 from a given binary array

Don't search for a formula – you'll probably never find something so specific. Instead, try to break up the task into smaller units. Since your arrays are binary, $$(A_i-B_i)^2 = \begin{...
2 votes

A data structure that makes finding close objects easy

Data structures designed to organize multi-dimensional data can help, for instance quad trees or, more generally, k-d-trees. It might also be possible to apply ideas from sweep-line algorithms, ...
  • 71.2k
2 votes

Nearest Neighbor Search in Spherical Coordinates

Due to accuracy complications as well as loss of information I cannot convert them to Cartesian coordinates. I don't understand this restriction. Converting to Cartesian coordinates uses essentially ...
  • 2,072
2 votes
Accepted

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

Distance metric learning It sounds like you want to learn a distance metric $D(\cdot,\cdot)$ on the items. If the human tells you that A is more similar to B than to C, then you learn that $D(A,B) &...
  • 145k
2 votes
Accepted

Find nearest neighbour in a radius

The K-D tree is a good data structure for solving this. However you can't blindly apply the search procedure only to the center point, you must be a bit smarter. While searching the K-D tree for your ...
  • 12.4k
2 votes

kdtree or balltree supporting insertion/deletion

My experience comes mainly from kd-trees. I think this answers part of your question and the attached image really visualizes the problem. When you construct the kd-tree initially the tree is ...
2 votes

kdtree or balltree supporting insertion/deletion

I am not sure about BallTrees, but kd-trees definitely support deletion (see my Java implementation here). I think the reason why it is often not implemented is that it is a lot more complex and may ...
  • 709
2 votes
Accepted

A nearest neighbor data structure for meshes

It suffices to store all of the triangles from all of the meshes in a nearest-neighbor data structure for triangles. Then, given a point P, find the nearest triangle, check which mesh that triangle ...
  • 145k
1 vote

Placing a point between two nearest ones

Don't add the point between the closest pair of points; add it between the endpoints of the closest edge.
1 vote
Accepted

In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance?

Cosine distance is common in Information Retrieval and other text-based scenarios because text is most easily represented as high dimensional sparse vectors in the word space. A few specific ...
1 vote

How to efficiently compute the most isolated point?

Use any algorithm for all nearest neighbors; then you can trivially solve your problem. Such an algorithm finds, for each data point, its nearest neighbor. The most isolated point is the one whose ...
  • 145k

Only top scored, non community-wiki answers of a minimum length are eligible