---
title: "Similarity Estimation Techniques from Rounding Algorithms (2002)"
description: "The paper asks how to build compact sketches of objects so that their similarity can be estimated… 42 references, cited by 104 papers here."
authors: ["Moses S. Charikar"]
year: 2002
venue: "STOC 2002"
source: "https://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarEstim.pdf"
doi: "10.1145/509907.509965"
licence: "author's copy (Princeton) — read only"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/charikar-2002-similarity-estimation-techniques-rounding/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/charikar-2002-similarity-estimation-techniques-rounding/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2002](https://md.research.elamur.ai/free/en/papers/2002/) / Similarity Estimation Techniques from Rounding Algorithms

# Similarity Estimation Techniques from Rounding Algorithms

**Authors:** Moses S. Charikar · **Year:** 2002 · **Venue:** STOC 2002 · **Licence:** author's copy (Princeton) — read only

**Links:** [Publisher's page](https://doi.org/10.1145/509907.509965) · [PDF](https://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarEstim.pdf) · [DOI 10.1145/509907.509965](https://doi.org/10.1145/509907.509965) · [OpenAlex](https://openalex.org/W2012833704)

**Citations:** 2,220 citations (OpenAlex, 2026-10-14) · [104](https://md.research.elamur.ai/free/en/papers/charikar-2002-similarity-estimation-techniques-rounding/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## 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 University](https://md.research.elamur.ai/free/en/universities/princeton-university/) — University, Princeton, United States · 113 works · 48,612 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 17,965 works · [👁️ Computer Vision and Pattern Recognition](https://md.research.elamur.ai/free/en/shelves/computer-science/computer-vision-and-pattern-recognition/) · 3,486 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-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.

```bibtex
@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}
}
```

- [← previous Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms](https://md.research.elamur.ai/free/en/papers/collins-2002-discriminative-training-methods-hidden-markov/)
- [next → Automatic Labeling of Semantic Roles](https://md.research.elamur.ai/free/en/papers/gildea-2002-automatic-labeling-semantic-roles/)
- [↑ back to papers of 2002](https://md.research.elamur.ai/free/en/papers/2002/)

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

*Updated 2 November 2026*