That's exactly the source i actually was referring to. They seem to imply that it is possible to construct a bunch of OR amplifications followed by a bunch of AND applifications but i did not seem to have found a practical explanation how to build this.
I understand their example about banding etc. which is essentially and example of AND amplification followed by OR. On Wed, Apr 27, 2011 at 10:22 PM, Randall McRee <[email protected]> wrote: > 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 >> >
