Scaling up all pairs similarity search

ABSTRACT

Given a large collection of sparse vector data in a high dimensional space, we investigate the problem of finding all pairs of vectors whose similarity score (as determined by a function such as cosine distance) is above a given threshold. We propose a simple algorithm based on novel indexing and optimization strategies that solves this problem without relying on approximation methods or extensive parameter tuning. We show the approach efficiently handles a variety of datasets across a wide setting of similarity thresholds, with large speedups over previous state-of-the-art approaches.

REFERENCES

• 1: Arvind Arasu , Venkatesh Ganti , Raghav Kaushik, Efficient exact set-similarity joins, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 2: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 3: Christian Böhm , Bernhard Braunmüller , Markus Breunig , Hans-Peter Kriegel, High performance clustering based on the similarity join, Proceedings of the ninth international conference on Information and knowledge management, p.298-305, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354832]
• 4: 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
• 5: Chris Buckley , Alan F. Lewit, Optimization of inverted vector searches, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.97-110, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253515]
• 6: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 7: Surajit Chaudhuri , Venkatesh Ganti , Raghav Kaushik, A Primitive Operator for Similarity Joins in Data Cleaning, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.5, April 03-07, 2006 [doi>10.1109/ICDE.2006.9]
• 8: Steve Chien , Nicole Immorlica, Semantic similarity between search engine queries using temporal correlation, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060752]
• 9: Shui-Lung Chuang , Lee-Feng Chien, Taxonomy generation for text segments: A practical web-based approach, ACM Transactions on Information Systems (TOIS), v.23 n.4, p.363-396, October 2005 [doi>10.1145/1095872.1095873]
• 10: Ronald Fagin , Ravi Kumar , D. Sivakumar, Efficient similarity search and classification via rank aggregation, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872795]
• 11: 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
• 12: 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]
• 13: Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Detectives: detecting coalition hit inflation attacks in advertising networks streams, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242606]
• 14: A. Moffat, R. Sacks-Davis, R. Wilkinson, & J. Zobel (1994). Retrieval of partial documents. In The Second Text REtrieval Conference, 181--190.
• 15: Alistair Moffat , Justin Zobel, Self-indexing inverted files for fast text retrieval, ACM Transactions on Information Systems (TOIS), v.14 n.4, p.349-379, Oct. 1996 [doi>10.1145/237496.237497]
• 16: Michael Persin, Document filtering for fast ranking, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.339-348, July 03-06, 1994, Dublin, Ireland
• 17: M. Persin, J. Zobel, & R. Sacks-Davis (1994). Fast document ranking for large scale information retrieval. In Proc. of the First Int'l Conf. on Applications of Databases, Lecture Notes in Computer Science v819, 253--266.
• 18: Raghu Ramakrishnan , Johannes Gehrke, Database Management Systems, McGraw-Hill Science/Engineering/Math, 2002
• 19: Mehran Sahami , Timothy D. Heilman, A web-based kernel function for measuring the similarity of short text snippets, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135834]
• 20: Ellen Spertus , Mehran Sahami , Orkut Buyukkokten, Evaluating similarity measures: a large-scale study in the orkut social network, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081956]
• 21: Sunita Sarawagi , Alok Kirpal, Efficient set joins on similarity predicates, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007652]
• 22: Trevor Strohman , Howard Turtle , W. Bruce Croft, Optimization strategies for complex queries, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076074]
• 23: Howard Turtle , James Flood, Query evaluation: strategies and optimizations, Information Processing and Management: an International Journal, v.31 n.6, p.831-850, Nov. 1995 [doi>10.1016/0306-4573(95)00020-H]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Performance

Keywords:
data mining, similarity join, similarity search