I'm reading one of the early LSH papers and I'm a little confused by the meaning of a "block". In particular, in the proof of theorem 1 in section 3.2 (p 522), what are the blocks being pointed to? Just hash buckets? The step I'm having trouble with is "The expected number of blocks allocated for $g_j$ which contain exclusively points from $P'$ does not exceed 2" - I'm having trouble parsing this sentence, even though the paper makes it sound trivial.

Am I missing something obvious?

  • 1
    $\begingroup$ Can you give a page number? $\:$ $\endgroup$ – user6973 Apr 19 '13 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.