A great reference is "Mining of Massive Datasets": http://infolab.stanford.edu/~ullman/mmds.html
See section 3.6.3, it answers your question (and more! :) ) Randy On Tue, Apr 26, 2011 at 9:01 PM, Dmitriy Lyubimov <[email protected]> wrote: > Hi, > with at least 2 other LSH threads around, i thought i might ask a question. > > So the theory talks about amplifying the functions by AND and OR . Say > for simplicity let's consider the cosine distance LSH family. each > hash function thus produces 1 bit. A natural (and i guess implied way) > of AND amplification is just to concatenate them into {1,0}^L. > > But i can't seem to find specifics for OR amplification. > > I can figure than AND- OR amplification may just implemented with > multiple hash function probes (like in any hash with multiple > functions). But the theory often also talks about OR-AND > amplification, and i can't think of the way actually doing OR first > (except for really converting it into Hamming distance and then try to > rehash based on that). > > What are possible techniques for the OR amplification? > > Thanks. > -Dmitriy >
