Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem
Moshe Dubiner · IEEE Transactions on Information Theory · 2010
The problem of finding high-dimensional approximate nearest neighbors is considered when the data is generated by some known probabilistic model. A large natural class of algorithms (bucketing codes) is investigated, Bucketing information is defined, and is proven to bound the performance of all bucketing codes. The bucketing information bound is asymptotically attained by some randomly constructed bucketing codes. The example ofnBernoulli(1/2) very long (lengthd→ ∞) sequences of bits is singled out. It is assumed thatn- 2msequences are completely independent, while the remaining2msequences are composed ofmdependent pairs. The interdependence within each pair is that their bits agree with probability1/2 0. A specific 2-D inequality (proven in another paper) implies that the exponent1/pcannot be lowered. Moreover, if one sequence out of each pair belongs to a known set ofn(2p-1)2sequences, pairing can be done using ordern1+∈comparisons!