Entropy based Nearest Neighbor Search in High Dimensions

Details Entropy based Nearest Neighbor Search in High Dimensions Entropy based Nearest Neighbor Search in High Dimensions

2005-10-07

arxiv.org/abs/cs/0510019v2

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper we study the problem of finding the approximate nearest neighbor of a query point in the high dimensional space, focusing on the Euclidean space. The earlier approaches use locality-preserving hash functions (that tend to map nearby points to the same value) to construct several hash tables to ensure that the query point hashes to the same bucket as its nearest neighbor in at least one table. Our approach is different -- we use one (or a few) hash table and hash several randomly chosen points in the neighborhood of the query point showing that at least one of them will hash to the bucket containing its nearest neighbor. We show that the number of randomly chosen points in the neighborhood of the query point $q$ required depends on the entropy of the hash value $h(p)$ of a random point $p$ at the same distance from $q$ at its nearest neighbor, given $q$ and the locality preserving hash function $h$ chosen randomly from the hash family. Precisely, we show that if the entropy $I(h(p)|q,h) = M$ and $g$ is a bound on the probability that two far-off points will hash to the same bucket, then we can find the approximate nearest neighbor in $O(n^\rho)$ time and near linear $\tilde O(n)$ space where $\rho = M/\log(1/g)$. Alternatively we can build a data structure of size $\tilde O(n^{1/(1-\rho)})$ to answer queries in $\tilde O(d)$ time. By applying this analysis to the locality preserving hash functions in and adjusting the parameters we show that the $c$ nearest neighbor can be computed in time $\tilde O(n^\rho)$ and near linear space where $\rho \approx 2.06/c$ as $c$ becomes large.

Affiliated with

Also associated with

No associations

Rating

Entropy based Nearest Neighbor Search in High Dimensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Entropy based Nearest Neighbor Search in High Dimensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Entropy based Nearest Neighbor Search in High Dimensions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-560963