# Find minimum distance match in sub-linear time in a data base

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.

• I found some solutions such as organizing the index into R-trees or kd-trees. May 4, 2017 at 18:16

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