Questions tagged [nearest-neighbour]

The point from the dataset that is closest to the query point.

Filter by
Sorted by
Tagged with
2 votes
1 answer
465 views

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

Let $A$ be a sorted array of $N$ values. I am interested in finding the index $j$ such that the elements $A_j, A_{j + 1}, ..., A_{j + k - 1}$ have the $k$ closest values to the given target value $T$. ...
user avatar
  • 175
2 votes
1 answer
43 views

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

I am looking for some clues as to the type of algorithm/data structure or general field of CS to look into... I have a collection of items that I would like to have a human subjectively compare such ...
user avatar
10 votes
1 answer
878 views

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

I've read in many papers on higher-dimensional nearest neighbor search that KD-Trees are exponential in K, but I can't seem to determine why. What I'm looking for is a solid runtime-complexity ...
user avatar
  • 200
4 votes
1 answer
788 views

Best data structure for high dimensional nearest neighbor search

I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also I'...
user avatar
  • 141
4 votes
1 answer
831 views

Find the closest string to a fixed set of strings

I want to find the closest string to a fixed set of strings. The strings are all equal in length, and the number of strings in the set is relatively small (compared to all the possible strings of the ...
user avatar
  • 218
3 votes
0 answers
516 views

Why is exact nearest neighbor search hard in high dimensional spaces?

I started research on nearest neighbor search in IR a couple of weeks ago. I am still very new to this field, but what I discovered so far from literature is: 1) For the exact nearest neighbor ...
user avatar
2 votes
1 answer
419 views

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

I'm not an computer scientist, but still use/have an algorithm to find the $k$ nearest neighbours from a cloud of $N$ points in $d$ (my case $d=3$) dimensional space using some distance measure (in my ...
user avatar
  • 121
0 votes
2 answers
209 views

How can I make k nearest neighbor queries fast on unit hypersphere?

I have $m$ points $D = \{x_1, \dots, x_m\}$ with $x_i \in \mathbb{R}^n$. After some preprocessing / building up data structures for those points, I get $T$ queries $y_i \in \mathbb{R}^n$ with $i=1, \...
user avatar
  • 2,300