An efficient filter for approximate membership checking

ABSTRACT

We consider the problem of identifying sub-strings of input text strings that approximately match with some member of a potentially large dictionary. This problem arises in several important applications such as extracting named entities from text documents and identifying biological concepts from biomedical literature. In this paper, we develop a filter-verification framework, and propose a novel in-memory filter structure. That is, we first quickly filter out sub-strings that cannot match with any dictionary member, and then verify the remaining sub-strings against the dictionary. Our method does not produce false negatives. We demonstrate the efficiency and effectiveness of our filter over real datasets, and show that it significantly outperforms the previous best-known methods in terms of both filtering power and computation time.

REFERENCES

• 1: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 2: Amihood Amir , Dmitry Keselman , Gad M. Landau , Moshe Lewenstein , Noa Lewenstein , Michael Rodeh, Text indexing and dictionary matching with one error, Journal of Algorithms, v.37 n.2, p.309-325, Nov. 2000 [doi>10.1006/jagm.2000.1104]
• 3: 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
• 4: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 5: Gerth Stølting Brodal , Leszek Gasieniec, Approximate Dictionary Queries, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.65-74, June 10-12, 1996
• 6: Kaushik Chakrabarti , Venkatesh Ganti , Jiawei Han , Dong Xin, Ranking objects based on relationships, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142516]
• 7: Amit Chandel , P. C. Nagesh , Sunita Sarawagi, Efficient Batch Top-k Search for Dictionary-based Entity Recognition, Proceedings of the 22nd International Conference on Data Engineering, p.28, April 03-07, 2006 [doi>10.1109/ICDE.2006.55]
• 8: 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]
• 9: Finding Interesting Associations without Support Pruning, Proceedings of the 16th International Conference on Data Engineering, p.489, February 28-March 03, 2000
• 10: 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]
• 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: 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: T. H. Haveliwala, A. Gionis, and P. Indyk. Scalable techniques for clustering the web. In WebDB (Informal Proceedings), pages 129--134, 2000.
• 14: Udi Manber , Sun Wu, An algorithm for approximate membership checking with application to password security, Information Processing Letters, v.50 n.4, p.191-197, May 25, 1994 [doi>10.1016/0020-0190(94)00032-8]
• 15: M. Narayanan and R. M. Karp. Gapped local similarity search with provable guarantees. In WABI, pages 74--86, 2004.
• 16: 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]
• 17: A. Singhal. Modern information retrieval: A brief overview. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 24(4):35--43, 2001.
• 18: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 19: A. C.-C. Yao and F. F. Yao. Dictionary loop-up with small errors. In CPM, pages 387--394, 1995.
• 20: X. Zhou, X. Zhang, and X. Hu. Maxmatcher: Biological concept extraction using approximate dictionary lookup. In PRICAI, pages 1145--1149, 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases

General Terms:
Algorithms

Keywords:
approximate membership checking, filtering, string match