Incremental maintenance of length normalized indexes for approximate string matching

ABSTRACT

Approximate string matching is a problem that has received a lot of attention recently. Existing work on information retrieval has concentrated on a variety of similarity measures TF/IDF, BM25, HMM, etc.) specifically tailored for document retrieval purposes. As new applications that depend on retrieving short strings are becoming popular(e.g., local search engines like YellowPages.com, Yahoo!Local, and Google Maps) new indexing methods are needed, tailored for short strings. For that purpose, a number of indexing techniques and related algorithms have been proposed based on length normalized similarity measures. A common denominator of indexes for length normalized measures is that maintaining the underlying structures in the presence of incremental updates is inefficient, mainly due to data dependent, precomputed weights associated with each distinct token and string. Incorporating updates usually is accomplished by rebuilding the indexes at regular time intervals. In this paper we present a framework that advocates lazy update propagation with the following key feature: Efficient, incremental updates that immediately reflect the new data in the indexes in a way that gives strict guarantees on the quality of subsequent query answers. More specifically, our techniques guarantee against false negatives and limit the number of false positives produced. We implement a fully working prototype and illustrate that the proposed ideas work really well in practice for real datasets.

REFERENCES

• 1: ]]Apache Lucene. http://lucene.apache.org/.
• 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: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 4: ]]R. A. Baeza-Yates and G. Navarro. Faster approximate string matching. Algorithmica, 23(2):127--158, 1999
• 5: 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]
• 6: 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]
• 7: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 8: Ahmed K. Elmagarmid , Panagiotis G. Ipeirotis , Vassilios S. Verykios, Duplicate Record Detection: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.19 n.1, p.1-16, January 2007 [doi>10.1109/TKDE.2007.9]
• 9: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 10: ]]FAST - Enterprise Search. http://www.fastsearch.com.
• 11: ]]Google. http://www.google.com.
• 12: 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
• 13: Marios Hadjieleftheriou , Amit Chandel , Nick Koudas , Divesh Srivastava, Fast Indexes and Algorithms for Set Similarity Selection Queries, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.267-276, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497435]
• 14: Nick Koudas , Amit Marathe , Divesh Srivastava, Flexible string matching against large databases in practice, Proceedings of the Thirtieth international conference on Very large data bases, p.1078-1086, August 31-September 03, 2004, Toronto, Canada
• 15: ]]N. Koudas, A. Marathe, and D. Srivastava. Propagating updates in SPIDER. In ICDE, pages 1146--1153, 2007.
• 16: Nick Koudas , Sunita Sarawagi , Divesh Srivastava, Record linkage: similarity measures and algorithms, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142599]
• 17: ]]M. Ley. DBLP database. http://dblp.uni-trier.de/xml.
• 18: Chen Li , Jiaheng Lu , Yiming Lu, Efficient Merging and Filtering Algorithms for Approximate String Searches, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.257-266, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497434]
• 19: ]]Oracle. Oracle Berkeley DB. http://www.oracle.com/technology/products/ berkeley-db/db/ index.html.
• 20: ]]S. E. Robertson, S. Walker, M. Hancock-Beaulieu, A. Gull, and M. Lau. Okapi at TREC. In Text REtrieval Conference (TREC), pages 21--30, 1992.
• 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: Xiaochun Yang , Bin Wang , Chen Li, Cost-based variable-length-gram selection for string collections to support approximate queries efficiently, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376655]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms

Keywords:
idf, inverted index, length normalization, string indexing, updates