Elamur Research⌕
☰
home / papers / 2002 / Similarity Estimation Techniques from Rounding Algorithms

Similarity Estimation Techniques from Rounding Algorithms

Paper · 2002 · Moses S. Charikar

Summary

The paper asks how to build compact sketches of objects so that their similarity can be estimated cheaply. It frames this as locality sensitive hashing (LSH): a random family of hash functions in which two objects collide with probability equal to their similarity. Charikar's key observation is that randomized rounding procedures for LP and SDP relaxations, used in approximation algorithms, can be read as such hash families.

The Goemans–Williamson random hyperplane method gives one-bit hashes for vectors that collide with probability 1 − θ/π, where θ is the angle between the vectors. This closely tracks cosine similarity, and comparing two objects reduces to the Hamming distance between their short bit signatures. Rounding schemes for classification with pairwise relationships yield hashes that approximate the Earth Mover Distance between distributions.

The paper also proves necessary conditions for LSH to exist, and it gives a simpler data structure for approximate nearest neighbor search in Hamming space. This technique, later popularized as SimHash, became a standard tool for near-duplicate detection and large-scale similarity search.

Key points

  • Core definition. An LSH family satisfies Pr[h(x)=h(y)] = sim(x, y). Min-wise independent permutations (Broder et al., built for near-duplicate removal in the Altavista index) are an instance of this for Jaccard set similarity.
  • Random hyperplane hashing.
    • Each hash outputs a single bit, so t hashes form a t-bit signature.
    • The similarity 1 − θ/π stays within a factor of 0.878 of cos θ.
    • The method works for general real vectors, not just sets.
  • Impossibility results. Necessary conditions on the similarity function show that no LSH scheme exists for the Dice or Overlap coefficients.
  • Earth Mover Distance. Hashing based on rounding for the Kleinberg–Tardos classification LP maps distributions over n points to single points. The expected distance between the hashed points is at least EMD and at most O(log n log log n) times EMD.
  • Nearest neighbor search. The proposed method keeps O(n^{1/(1+ε)}) randomly permuted, lexicographically sorted lists of bit vectors.
    • It matches the Indyk–Motwani bounds.
    • A single structure handles all search radii, with no reduction to multiple PLEB instances.
    • A weighted generalization of min-wise hashing is also given.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Princeton UniversityPrinceton · United States113 works · 48,612 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksComputer Vision and Pattern Recognition · 3,486 worksComputational Theory and Mathematics · 321 works

Cite

Cite as Moses S. Charikar. 2002. Similarity Estimation Techniques from Rounding Algorithms. STOC 2002.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1145/509907.509965

@inproceedings{charikar2002similarity,
  title = {{Similarity Estimation Techniques from Rounding Algorithms}},
  author = {Moses S. Charikar},
  booktitle = {STOC 2002},
  year = {2002},
  doi = {10.1145/509907.509965},
  url = {https://doi.org/10.1145/509907.509965}
}

References

42 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. N. Alon, P. B. Gibbons, Y. Matias, and M. Szegedy. Tracking Join and Self-Join Sizes in Limited Storage. Proc. 18th PODS pp. 10-20, 1999. find
  2. N. Alon, Y. Matias, and M. Szegedy. The Space Complexity of Approximating the Frequency Moments. JCSS 58(1): 137-147, 1999 find
  3. Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic application. Proc. 37th FOCS, pages 184–193, 1996. find
  4. Y. Bartal. On approximating arbitrary metrics by tree metrics. In Proc. 30th STOC, pages 161–168, 1998. find
  5. A. Z. Broder. On the resemblance and containment of documents. Proc. Compression and Complexity of SEQUENCES, pp. 21–29. IEEE Computer Society, 1997. find
  6. A. Z. Broder. Filtering near-duplicate documents. Proc. FUN 98, 1998. find
  7. A. Z. Broder, M. Charikar, A. Frieze, and M. Mitzenmacher. Min-wise independent permutations. Proc. 30th STOC, pp. 327–336, 1998. find
  8. A. Z. Broder, S. C. Glassman, M. S. Manasse, and G. Zweig. Syntactic clustering of the Web. Proc. 6th Int’l World Wide Web Conference, pp. 391–404, 1997. find
  9. A. Z. Broder, R. Krauthgamer, and M. Mitzenmacher. Improved classification via connectivity information. Proc. 11th SODA, pp. 576-585, 2000. find
  10. G. Calinescu, H. J. Karloff, and Y. Rabani. Approximation algorithms for the 0-extension problem. Proc. 11th SODA, pp. 8-16, 2000. find
  11. C. Chekuri, S. Khanna, J. Naor, and L. Zosin. Approximation algorithms for the metric labeling problem via a new linear programming formulation. Proc. 12th SODA, pp. 109-118, 2001. find
  12. Z. Chen, H. V. Jagadish, F. Korn, N. Koudas, S. Muthukrishnan, R. T. Ng, and D. Srivastava. Counting Twig Matches in a Tree. Proc. 17th ICDE pp. 595-604. 2001. find
  13. Z. Chen, F. Korn, N. Koudas, and S. Muthukrishnan. Selectivity Estimation for Boolean Queries. Proc. 19th PODS, pp. 216-225, 2000. find
  14. E. Cohen, M. Datar, S. Fujiwara, A. Gionis, P. Indyk, R. Motwani, J. D. Ullman, and C. Yang. Finding Interesting Associations without Support Pruning. Proc. 16th ICDE pp. 489-499, 2000. find
  15. S. Cohen and L. Guibas. The Earth Mover’s Distance under Transformation Sets. Proc. 7th IEEE Intnl. Conf. Computer Vision, 1999. find
  16. S. Cohen and L. Guibas. The Earth Mover’s Distance: Lower Bounds and Invariance under Translation. Tech. report STAN-CS-TR-97-1597, Dept. of Computer Science, Stanford University, 1997. find
  17. L. Engebretsen, P. Indyk and R. O’Donnell. Derandomized dimensionality reduction with applications. To appear in Proc. 13th SODA, 2002. find
  18. P. B. Gibbons and Y. Matias. Synopsis Data Structures for Massive Data Sets. Proc. 10th SODA pp. 909–910, 1999. find
  19. A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. J. Strauss. Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries. Proc. 27th VLDB pp. 79-88, 2001. find
  20. A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. J. Strauss. QuickSAND: Quick Summary and Analysis of Network Data. DIMACS Technical Report 2001-43, November 2001. find
  21. A. C. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan, and M. J. Strauss. Fast, Small-Space Algorithms for Approximate Histogram Maintenance. these proceedings. find
  22. A. Gionis, D. Gunopulos, and N. Koudas. Efficient and Tunable Similar Set Retrieval. Proc. SIGMOD Conference 2001. find
  23. A. Gionis, P. Indyk, and R. Motwani. Similarity Search in High Dimensions via Hashing. Proc. 25th VLDB pp. 518-529, 1999. find
  24. M. X. Goemans and D. P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. JACM 42(6): 1115-1145, 1995. find
  25. S. Guha, N. Mishra, R. Motwani, and L. O’Callaghan. Clustering data streams. Proc. 41st FOCS, pp. 359–366, 2000. find
  26. A. Gupta and Éva Tardos. A constant factor approximation algorithm for a class of classification problems. Proc. 32nd STOC, pp. 652–658, 2000. find
  27. T. H. Haveliwala, A. Gionis, and P. Indyk. Scalable Techniques for Clustering the Web. Proc. 3rd WebDB, pp. 129-134, 2000. find
  28. P. Indyk. A small approximately min-wise independent family of hash functions. Proc. 10th SODA, pp. 454–456, 1999. find
  29. P. Indyk. On approximate nearest neighbors in non-Euclidean spaces. Proc. 40th FOCS, pp. 148-155, 1999. find
  30. P. Indyk. Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation. Proc. 41st FOCS, 189-197, 2000. find
  31. Indyk, P., Motwani, R. Approximate nearest neighbors: towards removing the curse of dimensionality. Proc. 30th STOC pp. 604–613, 1998. find
  32. P. Indyk, R. Motwani, P. Raghavan, and S. Vempala. Locality-Preserving Hashing in Multidimensional Spaces. Proc. 29th STOC, pp. 618–625, 1997. find
  33. J. M. Kleinberg and Éva Tardos Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields. Proc. 40th FOCS, pp. 14–23, 1999. find
  34. N. Linial and O. Sasson. Non-Expansive Hashing. Combinatorica 18(1): 121-132, 1998. find
  35. N. Nisan. Pseudorandom sequences for space bounded computations. Combinatorica, 12:449–461, 1992. find
  36. Y. Rubner. Perceptual Metrics for Image Database Navigation. Phd Thesis, Stanford University, May 1999 find
  37. Y. Rubner, L. J. Guibas, and C. Tomasi. The Earth Mover’s Distance, Multi-Dimensional Scaling, and Color-Based Image Retrieval. Proc. of the ARPA Image Understanding Workshop, pp. 661-668, 1997. find
  38. Y. Rubner, C. Tomasi. Texture Metrics. Proc. IEEE International Conference on Systems, Man, and Cybernetics, 1998, pp. 4601-4607. find
  39. Y. Rubner, C. Tomasi, and L. J. Guibas. A Metric for Distributions with Applications to Image Databases. Proc. IEEE Int. Conf. on Computer Vision, pp. 59-66, 1998. find
  40. Y. Rubner, C. Tomasi, and L. J. Guibas. The Earth Mover’s Distance as a Metric for Image Retrieval. Tech. Report STAN-CS-TN-98-86, Dept. of Computer Science, Stanford University, 1998. find
  41. M. Ruzon and C. Tomasi. Color edge detection with the compass operator. Proc. IEEE Conf. Computer Vision and Pattern Recognition, 2:160-166, 1999. find
  42. M. Ruzon and C. Tomasi. Corner detection in textured color images. Proc. IEEE Int. Conf. Computer Vision, 2:1039-1045, 1999. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/charikar-2002-similarity-estimation-techniques-rounding/