(MATH) A locality sensitive hashing scheme is a distribution on a
family $\F$ of hash functions operating on a collection of objects,
such that for two objects x,y, Prh&egr;Fh(x) = h(y) = sim(x,y),
where sim(x,y) &egr; 0,1 is some similarity function defined on
the collection of objects. Such a scheme leads to a compact representation
of objects so that similarity of objects can be estimated from their
compact sketches, and also leads to efficient algorithms for approximate
nearest neighbor search and clustering. Min-wise independent permutations
provide an elegant construction of such a locality sensitive hashing
scheme for a collection of subsets with the set similarity measure
sim(A,B) = |A &Pgr; B||A &Pgr B|.(MATH) We show that rounding
algorithms for LPs and SDPs used in the context of approximation
algorithms can be viewed as locality sensitive hashing schemes for
several interesting collections of objects. Based on this insight,
we construct new locality sensitive hashing schemes for:...
%0 Conference Paper
%1 Charikar2002
%A Charikar, Moses S.
%B STOC '02: Proceedings of the thiry-fourth annual ACM symposium on
Theory of computing
%C New York, NY, USA
%D 2002
%I ACM
%K imported
%P 380--388
%R http://doi.acm.org/10.1145/509907.509965
%T Similarity estimation techniques from rounding algorithms
%X (MATH) A locality sensitive hashing scheme is a distribution on a
family $\F$ of hash functions operating on a collection of objects,
such that for two objects x,y, Prh&egr;Fh(x) = h(y) = sim(x,y),
where sim(x,y) &egr; 0,1 is some similarity function defined on
the collection of objects. Such a scheme leads to a compact representation
of objects so that similarity of objects can be estimated from their
compact sketches, and also leads to efficient algorithms for approximate
nearest neighbor search and clustering. Min-wise independent permutations
provide an elegant construction of such a locality sensitive hashing
scheme for a collection of subsets with the set similarity measure
sim(A,B) = |A &Pgr; B||A &Pgr B|.(MATH) We show that rounding
algorithms for LPs and SDPs used in the context of approximation
algorithms can be viewed as locality sensitive hashing schemes for
several interesting collections of objects. Based on this insight,
we construct new locality sensitive hashing schemes for:...
%@ 1-58113-495-9
@inproceedings{Charikar2002,
abstract = {(MATH) A locality sensitive hashing scheme is a distribution on a
family $\F$ of hash functions operating on a collection of objects,
such that for two objects x,y, Prh&egr;F[h(x) = h(y)] = sim(x,y),
where sim(x,y) &egr; [0,1] is some similarity function defined on
the collection of objects. Such a scheme leads to a compact representation
of objects so that similarity of objects can be estimated from their
compact sketches, and also leads to efficient algorithms for approximate
nearest neighbor search and clustering. Min-wise independent permutations
provide an elegant construction of such a locality sensitive hashing
scheme for a collection of subsets with the set similarity measure
sim(A,B) = \frac{|A &Pgr; B|}{|A &Pgr B|}.(MATH) We show that rounding
algorithms for LPs and SDPs used in the context of approximation
algorithms can be viewed as locality sensitive hashing schemes for
several interesting collections of objects. Based on this insight,
we construct new locality sensitive hashing schemes for:...},
added-at = {2013-08-04T14:35:26.000+0200},
address = {New York, NY, USA},
author = {Charikar, Moses S.},
biburl = {https://www.bibsonomy.org/bibtex/2e8f930208a07b54c3ecc8b36c78fdb61/francesco.k},
booktitle = {STOC '02: Proceedings of the thiry-fourth annual ACM symposium on
Theory of computing},
doi = {http://doi.acm.org/10.1145/509907.509965},
file = {:C\:\\Users\\D051450\\Desktop\\Aletheia\\Literature\\p380-charikar.pdf:PDF},
interhash = {72edecbc6593303ba15b76d9e61995ef},
intrahash = {e8f930208a07b54c3ecc8b36c78fdb61},
isbn = {1-58113-495-9},
keywords = {imported},
location = {Montreal, Quebec, Canada},
pages = {380--388},
publisher = {ACM},
timestamp = {2013-08-04T14:35:26.000+0200},
title = {Similarity estimation techniques from rounding algorithms},
year = 2002
}