Similarity estimation techniques from rounding algorithms

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, Pr_h&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:<ol>

A collection of vectors with the distance between → \over u and → \over v measured by Ø(→ \over u, → \over v)/&pgr;, where Ø(→ \over u, → \over v) is the angle between → \over u) and → \over v). This yields a sketching scheme for estimating the cosine similarity measure between two vectors, as well as a simple alternative to minwise independent permutations for estimating set similarity.

A collection of distributions on n points in a metric space, with distance between distributions measured by the Earth Mover Distance (EMD), (a popular distance measure in graphics and vision). Our hash functions map distributions to points in the metric space such that, for distributions P and Q, EMD(P,Q) &xie; E_h&egr;\F [d(h(P),h(Q))] &xie; O(log n log log n). EMD(P, Q).

</ol>.

REFERENCES

• 1: Noga Alon , Phillip B. Gibbons , Yossi Matias , Mario Szegedy, Tracking join and self-join sizes in limited storage, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.10-20, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303978]
• 2: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 3: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 4: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 5: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 6: A. Z. Broder. Filtering near-duplicate documents. Proc. FUN 98, 1998.
• 7: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.327-336, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276781]
• 8: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 9: Andrei Z. Broder , Robert Krauthgamer , Michael Mitzenmacher, Improved classification via connectivity information, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.576-585, January 09-11, 2000, San Francisco, California, United States
• 10: Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation algorithms for the 0-extension problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.8-16, January 07-09, 2001, Washington, D.C., United States
• 11: Chandra Chekuri , Sanjeev Khanna , Joseph Naor , Leonid Zosin, Approximation algorithms for the metric labeling problem via a new linear programming formulation, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.109-118, January 07-09, 2001, Washington, D.C., United States
• 12: Zhiyuan Chen , H. V. Jagadish , Flip Korn , Nick Koudas , S. Muthukrishnan , Raymond T. Ng , Divesh Srivastava, Counting Twig Matches in a Tree, Proceedings of the 17th International Conference on Data Engineering, p.595-604, April 02-06, 2001
• 13: Zhiyuan Chen , Nick Koudas , Flip Korn , S. Muthukrishnan, Selectively estimation for Boolean queries, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.216-225, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335225]
• 14: Finding Interesting Associations without Support Pruning, Proceedings of the 16th International Conference on Data Engineering, p.489, February 28-March 03, 2000
• 15: Scott Cohen , Leonidas Guibas, The Earth Mover's Distance under Transformation Sets, Proceedings of the International Conference on Computer Vision-Volume 2, p.1076, September 20-25, 1999
• 16: Scott Cohen , Leonidas Guibas, The Earth Mover''s Distance: Lower Bounds and Invariance under Translation, Stanford University, Stanford, CA, 1997
• 17: Lars Engebretsen , Piotr Indyk , Ryan O'Donnell, Derandomized dimensionality reduction with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.705-712, January 06-08, 2002, San Francisco, California
• 18: Phillip B. Gibbons , Yossi Matias, Synopsis data structures for massive data sets, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.909-910, January 17-19, 1999, Baltimore, Maryland, United States
• 19: Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin Strauss, Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.79-88, September 11-14, 2001
• 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.
• 21: Anna C. Gilbert , Sudipto Guha , Piotr Indyk , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509966]
• 22: Aristides Gionis , Dimitrios Gunopulos , Nick Koudas, Efficient and tumble similar set retrieval, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.247-258, May 21-24, 2001, Santa Barbara, California, United States
• 23: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 24: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 25: S. Guha , N. Mishra , R. Motwani , L. O'Callaghan, Clustering data streams, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.359, November 12-14, 2000
• 26: Anupam Gupta , Éva Tardos, A constant factor approximation algorithm for a class of classification problems, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.652-658, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335397]
• 27: T. H. Haveliwala, A. Gionis, and P. Indyk. Scalable Techniques for Clustering the Web. Proc. 3rd WebDB, pp. 129--134, 2000.
• 28: Piotr Indyk, A small approximately min-wise independent family of hash functions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.454-456, January 17-19, 1999, Baltimore, Maryland, United States
• 29: P. Indyk, On Approximate Nearest Neighbors in Non-Euclidean Spaces, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.148, November 08-11, 1998
• 30: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 31: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 32: Piotr Indyk , Rajeev Motwani , Prabhakar Raghavan , Santosh Vempala, Locality-preserving hashing in multidimensional spaces, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.618-625, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258656]
• 33: Jon Kleinberg , Eva Tardos, Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.14, October 17-18, 1999
• 34: N. Linial and O. Sasson. Non-Expansive Hashing. Combinatorica 18(1): 121--132, 1998.
• 35: N. Nisan. Pseudorandom sequences for space bounded computations. Combinatorica, 12:449--461, 1992.
• 36: Yossi (Joseph) Rubner , Carlo Tomasi, Perceptual metrics for image database navigation, 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.
• 38: Y. Rubner, C. Tomasi. Texture Metrics. Proc. IEEE International Conference on Systems, Man, and Cybernetics, 1998, pp. 4601--4607.
• 39: Yossi Rubner , Carlo Tomasi , Leonidas J. Guibas, A Metric for Distributions with Applications to Image Databases, Proceedings of the Sixth International Conference on Computer Vision, p.59, January 04-07, 1998
• 40: Yossi Rubner , Carlo Tomasi , Leonidas J. Guibas, The Earth Mover''s Distance as a Metric for Image Retrieval, Stanford University, Stanford, CA, 1998
• 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.
• 42: Mark A. Ruzon , Carlo Tomasi, Corner Detection in Textured Color Images, Proceedings of the International Conference on Computer Vision-Volume 2, p.1039, September 20-25, 1999

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Set theory

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

General Terms:
Algorithms, Experimentation, Performance, Theory