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

Computer Science – Information Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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

Scientific paper

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/20. 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!

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Bucketing Coding and Information Theory for the Statistical High Dimensional Nearest Neighbor Problem 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 Bucketing Coding and Information Theory for the Statistical High Dimensional Nearest Neighbor Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bucketing Coding and Information Theory for the Statistical High Dimensional Nearest Neighbor Problem will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-680002

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.