# Tag Info

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 ...
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 ...

### 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, ...

### 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 ...
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) &...
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 ...

### 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 ...

### 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 ...
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 ...
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, ...
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 ...
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 ...

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