The near-neighbors tag has no wiki summary.
1
vote
1answer
267 views
Simple k-nearest-neighbor algorithm for euclidean data with highly variable density?
An elaboration on this question, but with more constraints.
The idea is the same, to find a simple, fast algorithm for k-nearest-neighbors in 2 euclidean dimensions. The bucketing grid seems to work ...
8
votes
1answer
113 views
Dynamic planar exact k-nearest neighbors for pathological data
What are the best known results for a data structure offering the following operations on sets of points in 2-dimensional euclidean space:
$insert(x)$
$delete(x)$
$nearest(k,x)$ (where $k$ is an ...
6
votes
2answers
380 views
Calculating the distance to the kth nearest neighbor for all points in the set
For a machine learning application, my group needs to calculate the Euclidean distance to the $k$th nearest neighbor in a set $X$ for each $x \in (X \cup Y) \subset \mathbb R^d$ (for $d$ between 5 and ...
2
votes
1answer
170 views
What data structures exist for fast calculation of distances between multi-dimensional points
I'm writing a program that receives data over a network connection. Every data point is simply a 4 dimensional vertex, lets call the dimensions X,Y,Z,W. The values of each dimension are exponentially ...
4
votes
1answer
197 views
Does kd tree requires triangular inequality for finding k-nearest neighbors
I have 3-dimensional data I want to store in a kd-tree. Additionally I have a domain-specific distance function in this space for which I have a hard time to prove the triangular inequality. Here is ...
5
votes
3answers
246 views
Best algorithm for calculating lists of neighbours
Given a collection of thousands of points in 3D, I need to get the list of neighbours for each particle that fall inside some cutoff value (in terms of euclidean distance), and if possible, sorted ...
9
votes
4answers
446 views
Costs of performing approx. nearest neighbor search in a skip quadtree
NOTE: The question has been restated in my answers: Assuming now that we can find the lowest sibling ancestors in $O(1)$ time, can the ANN be really performed in $O(\log n)$?
Quadtrees are ...
1
vote
1answer
199 views
Compare similar N-Dimensional vector in a database
I want to compute Euclidian distance between similar vectors in a database (SQLite).
So each column in the database is a value from my vector.
The first problem appears, I have a large number of ...
