2
$\begingroup$

The title seems a little vague. So let me explain the question in detail.

Suppose you have a data base. Each record in the data base is $<\mathbf{x},data>$, where $\mathbf{x}$ is an $n$-dimensional index vector.

A query is also an $n$-dimensional vector $\mathbf{y}$. So given the query $\mathbf{y}$, the data base will return the record $i$ such that $\mathbf{x}_i$ and $\mathbf{y}$ have minimum distance. (It can be any distance. But let's focus on Euclidean distance here).

The trivial solution is to scan every record in the data base and compute the distance. This will introduce linear complexity with regard to the number of total records in the data base.

So is there any sub-linear algorithms to solve this problem (approximately)? For example, if the dimension $n=1$, we can organize the index in data structure such as binary search tree. But for dimension $n>1$, can we also organize the index into some special data structure?

Thanks for you time.

Improve this question
$\endgroup$
1
  • $\begingroup$ I found some solutions such as organizing the index into R-trees or kd-trees. $\endgroup$
    – Paradox
    May 4, 2017 at 18:16

1 Answer 1

Reset to default
1
$\begingroup$

This problem is exactly solved by the k-d tree, which organizes points in $k$ dimensions with logarithmic lookup time.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The k-d tree is indeed relevant, but there are no guarantees that you can find the nearest neighbor in logarithmic lookup time -- in fact, the lookup time can be arbitrarily bad. You might be thinking of results that if the points in the database are randomly distributed then finding a nearest neighbor might take logarithmic time (I can't personally vouch for that), but that's a significant "if" -- in practice data often isn't distributed randomly. $\endgroup$
    – D.W. ♦
    May 5, 2017 at 19:06
  • $\begingroup$ @D.W. The wiki mentioned logarithmic average time, that's why I mentioned it. Does there exist any data structure with guaranteed logarithmic time nearest neighbour search in the worst case? If not, is it proven to be impossible? $\endgroup$
    – orlp
    May 5, 2017 at 19:15
  • $\begingroup$ As far as I know, no such data structure is known. Due to the curse of dimensionality, the situation is very hard, in high dimensions. I don't know what the current-best results on worst-case complexity on nearest-neighbor search are, but if I recall correctly, they're pretty bad, and I have a recollection that it's hard to beat the trivial linear-scan algorithm in practice if the number of dimensions is large. $\endgroup$
    – D.W. ♦
    May 5, 2017 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.