Questions tagged [near-neighbors]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
85 views

What algorithms are there for ANN?

I'm a software engineer working on a large project for which one of the subcomponents involves approximately solving the nearest neighbors problem (to a factor of $1+\epsilon$). I was wondering what ...
Jaclyn's user avatar
  • 11
1 vote
1 answer
96 views

Query Phase of Multi-Level Hashing

I am trying to understand the fundamentals of multilevel Locality Sensitive Hashing. It is defined in the paper paper (page no-6). A Multi-level LSH data structure for $S$ is set up in the following ...
David's user avatar
  • 113
4 votes
1 answer
241 views

Binary Trees for Nearest Neighbor Search

Given points $x_1, ..., x_n \in \mathbb{R}^d$, consider a binary decision tree $T$ on $\mathbb{R}^d$ with $L$ leaves, i.e. for a point $y \in \mathbb{R}^d$ at every node of the tree, we check whether $...
Claudio Moneo's user avatar
3 votes
0 answers
628 views

Time Complexity for Nearest Neighbor Searches in kd-trees

Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof. In order to calculate the average number of ...
user1494080's user avatar
1 vote
1 answer
895 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 ...
donnyton's user avatar
  • 161
8 votes
1 answer
181 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 ...
jbapple's user avatar
  • 11.2k
9 votes
2 answers
2k 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 ...
Danica's user avatar
  • 193
2 votes
1 answer
916 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 ...
slayton's user avatar
  • 123
4 votes
1 answer
532 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 ...
steffen's user avatar
  • 143
6 votes
3 answers
300 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 ...
Open the way's user avatar
10 votes
4 answers
1k 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 efficient ...
0__'s user avatar
  • 173
1 vote
1 answer
1k 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 ...
Kirell's user avatar
  • 121