Bucketing Coding and Information Theory for the Statistical High Dimensional Nearest Neighbor Problem

Abstract

Consider the problem of finding high dimensional approximate nearest neighbors, where the data is generated by some known probabilistic model. We will investigate a large natural class of algorithms which we call bucketing codes. We will define bucketing information, prove that it bounds the performance of all bucketing codes, and that the bucketing information bound can be asymptotically attained by randomly constructed bucketing codes. For example suppose we have n Bernoulli(1/2) very long (length d-->infinity) sequences of bits. Let n-2m sequences be completely independent, while the remaining 2m sequences are composed of m independent pairs. The interdependence within each pair is that their bits agree with probability 1/2<p<=1. It is well known how to find most pairs with high probability by performing order of n^{\log_{2}2/p} comparisons. We will see that order of n^{1/p+ε} comparisons suffice, for any ε>0. Moreover if one sequence out of each pair belongs to a a known set of n^{(2p-1)^{2}-ε} sequences, than pairing can be done using order n comparisons!

Manuscript submitted to IEEE Transactions on Information Theory on March 3, 2007; revised August 27, 2007

Cited by in corpus (9)

• Practical and Optimal LSH for Angular Distance
• Tradeoffs for nearest neighbors on the sphere
• Set Similarity Search Beyond MinHash
• Detecting the large entries of a sparse covariance matrix in sub-quadratic time
• An Illuminating Algorithm for the Light Bulb Problem
• A New Algorithm for Finding Closest Pair of Vectors
• Graph-based time-space trade-offs for approximate near neighbors
• Algorithms for Similarity Search and Pseudorandomness
• Polytopes, lattices, and spherical codes for the nearest neighbor problem