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 ...
D.W.♦
- 156k
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 ...
- 81.4k
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_{...
- 527
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 ...
- 887
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 ...
D.W.♦
- 156k
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.
D.W.♦
- 156k
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,425
3
votes
Find the closest string to a fixed set of strings
This is a nearest-neighbor problem, and there are a variety of algorithms for the problem. The simplest is a k-d tree, and there are more sophisticated data structures as well. Another approach is ...
D.W.♦
- 156k
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 ...
- 275k
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 ...
- 764
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' (...
- 764
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 ...
- 854
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 ...
- 764
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 ...
D.W.♦
- 156k
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. ...
- 764
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+...
D.W.♦
- 156k
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 ...
- 275k
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{...
- 81.4k
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, ...
- 72k
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) &...
D.W.♦
- 156k
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.7k
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 ...
- 254
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 ...
- 764
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 ...
D.W.♦
- 156k
1
vote
Is this computational complexity of the k-NN (custom distance) correct?
The running time of a nearest neighbor classifier is the time to compute the distance between two examples, multiplied by the number of pairs of examples you need to compute the distance between. So, ...
D.W.♦
- 156k
1
vote
Condensed Nearest Neighbor Explanation
Z is not the array of misclassified points. Try working through an example, and be careful and precise when making statements like that; while you can talk about ...
D.W.♦
- 156k
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.
- 81.4k
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 ...
- 589
Only top scored, non community-wiki answers of a minimum length are eligible