Ed-Join: an efficient algorithm for similarity joins with edit distance constraints

ABSTRACT

There has been considerable interest in similarity join in the research community recently. Similarity join is a fundamental operation in many application areas, such as data integration and cleaning, bioinformatics, and pattern recognition. We focus on efficient algorithms for similarity join with edit distance constraints. Existing approaches are mainly based on converting the edit distance constraint to a weaker constraint on the number of matching q-grams between pair of strings.

In this paper, we propose the novel perspective of investigating mismatching q-grams. Technically, we derive two new edit distance lower bounds by analyzing the locations and contents of mismatching q-grams. A new algorithm, Ed-Join, is proposed that exploits the new mismatch-based filtering methods; it achieves substantial reduction of the candidate sizes and hence saves computation time. We demonstrate experimentally that the new algorithm outperforms alternative methods on large-scale real datasets under a wide range of parameter settings.

REFERENCES

• 1: A. Andoni , M. Deza , A. Gupta , P. Indyk , S. Raskhodnikova, Lower bounds for embedding edit distance into normed spaces, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 2: 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
• 3: Roberto J. Bayardo , Yiming Ma , Ramakrishnan Srikant, Scaling up all pairs similarity search, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242591]
• 4: Mikhail Bilenko , Raymond Mooney , William Cohen , Pradeep Ravikumar , Stephen Fienberg, Adaptive Name Matching in Information Integration, IEEE Intelligent Systems, v.18 n.5, p.16-23, September 2003 [doi>10.1109/MIS.2003.1234765]
• 5: Christian Böhm , Bernhard Braunmüller , Florian Krebs , Hans-Peter Kriegel, Epsilon grid order: an algorithm for the similarity join on massive high-dimensional data, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.379-388, May 21-24, 2001, Santa Barbara, California, United States
• 6: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Computer Networks and ISDN Systems, v.29 n.8-13, p.1157-1166, Sep. 1997
• 7: Stefan Burkhardt , Juha Kärkkäinen, One-Gapped q-Gram Filtersfor Levenshtein Distance, Proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching, p.225-234, July 03-05, 2002
• 8: Amit Chandel , Oktie Hassanzadeh , Nick Koudas , Mohammad Sadoghi , Divesh Srivastava, Benchmarking declarative approximate selection predicates, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247521]
• 9: 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]
• 10: Surajit Chaudhuri , Bee-Chung Chen , Venkatesh Ganti , Raghav Kaushik, Example-driven design of efficient record matching queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 11: S. Chaudhuri, V. Ganti, and R. Kaushik. Data debugger: An operator-centric approach for data quality solutions. IEEE Data Eng. Bull., 29(2):60--66, 2006.
• 12: Surajit Chaudhuri , Venkatesh Ganti , Raghav Kaushik, A Primitive Operator for Similarity Joins in Data Cleaning, Proceedings of the 22nd International Conference on Data Engineering, p.5, April 03-07, 2006 [doi>10.1109/ICDE.2006.9]
• 13: 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
• 14: Luis Gravano , Panagiotis G. Ipeirotis , H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Approximate String Joins in a Database (Almost) for Free, Proceedings of the 27th International Conference on Very Large Data Bases, p.491-500, September 11-14, 2001
• 15: L. Gravano, P. G. Ipeirotis, H. V. Jagadish, N. Koudas, S. Muthukrishnan, and D. Srivastava. Approximate string joins in a database (almost) for free (erratum). Technical Report CUCS-011-03, Columbia University, 2003.
• 16: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 17: Sven Helmer , Guido Moerkotte, Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates, Proceedings of the 23rd International Conference on Very Large Data Bases, p.386-395, August 25-29, 1997
• 18: Monika Henzinger, Finding near-duplicate web pages: a large-scale evaluation of algorithms, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148222]
• 19: Mauricio A. Hernández , Salvatore J. Stolfo, Real-world Data is Dirty: Data Cleansing and The Merge/Purge Problem, Data Mining and Knowledge Discovery, v.2 n.1, p.9-37, January 1998 [doi>10.1023/A:1009761603038]
• 20: Hongrae Lee , Raymond T. Ng , Kyuseok Shim, Extending q-grams to estimate selectivity of string matching with low edit distance, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 21: Chen Li , Bin Wang , Xiaochun Yang, VGRAM: improving performance of approximate queries on string collections using variable-length grams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 22: Nikos Mamoulis, Efficient processing of joins on set-valued attributes, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872778]
• 23: W. J. Masek and M. Paterson. A faster algorithm computing string edit distances. J. Comput. Syst. Sci., 20(1):18--31, 1980.
• 24: Sergey Melnik , Hector Garcia-Molina, Adaptive algorithms for set containment joins, ACM Transactions on Database Systems (TODS), v.28 n.1, p.56-99, March 2003 [doi>10.1145/762471.762474]
• 25: Gene Myers, A fast bit-vector algorithm for approximate string matching based on dynamic programming, Journal of the ACM (JACM), v.46 n.3, p.395-415, May 1999 [doi>10.1145/316542.316550]
• 26: Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001 [doi>10.1145/375360.375365]
• 27: M. V. Ramakrishna , Justin Zobel, Performance in Practice of String Hashing Functions, Proceedings of the Fifth International Conference on Database Systems for Advanced Applications (DASFAA), p.215-224, April 01-04, 1997
• 28: Karthikeyan Ramasamy , Jignesh M. Patel , Jeffrey F. Naughton , Raghav Kaushik, Set Containment Joins: The Good, The Bad and The Ugly, Proceedings of the 26th International Conference on Very Large Data Bases, p.351-362, September 10-14, 2000
• 29: Sunita Sarawagi , Anuradha Bhamidipaty, Interactive deduplication using active learning, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775087]
• 30: 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]
• 31: Esko Ukkonen, On Approximate String Matching, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.487-495, August 21-27, 1983
• 32: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
• 33: W. E. Winkler. The state of record linkage and current research problems. Technical report, U.S. Bureau of the Census, 1999.
• 34: Chuan Xiao , Wei Wang , Xuemin Lin , Jeffrey Xu Yu, Efficient similarity joins for near duplicate detection, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367516]
• 35: Justin Zobel , Alistair Moffat, Inverted files for text search engines, ACM Computing Surveys (CSUR), v.38 n.2, p.6-es, 2006 [doi>10.1145/1132956.1132959]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

General Terms:
Algorithms, Design, Management, Measurement, Performance