  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+\epsilon}
comparisons suffice, for any \epsilon>0. Moreover if one sequence out of each
pair belongs to a a known set of n^{(2p-1)^{2}-\epsilon} sequences, than
pairing can be done using order n comparisons!
