Efficient approximate entity extraction with edit distance constraints

ABSTRACT

Named entity recognition aims at extracting named entities from unstructured text. A recent trend of named entity recognition is finding approximate matches in the text with respect to a large dictionary of known entities, as the domain knowledge encoded in the dictionary helps to improve the extraction performance.

In this paper, we study the problem of approximate dictionary matching with edit distance constraints. Compared to existing studies using token-based similarity constraints, our problem definition enables us to capture typographical or orthographical errors, both of which are common in entity extraction tasks yet may be missed by token-based similarity constraints. Our problem is technically challenging as existing approaches based on q-gram filtering have poor performance due to the existence of many short entities in the dictionary. Our proposed solution is based on an improved neighborhood generation method employing novel partitioning and prefix pruning techniques. We also propose an efficient document processing algorithm that minimizes unnecessary comparisons and enumerations and hence achieves good scalability. We have conducted extensive experiments on several publicly available named entity recognition datasets. The proposed algorithm outperforms alternative approaches by up to an order of magnitude.

REFERENCES

• 1: Sanjay Agrawal , Kaushik Chakrabarti , Surajit Chaudhuri , Venkatesh Ganti, Scalable ad-hoc entity extraction from text collections, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453958]
• 2: Einat Amitay , Nadav Har'El , Ron Sivan , Aya Soffer, Web-a-where: geotagging web content, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009040]
• 3: Arvind Arasu , Surajit Chaudhuri , Kris Ganjam , Raghav Kaushik, Incorporating string transformations in record matching, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376742]
• 4: 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
• 5: 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]
• 6: Philip A. Bernstein , Dah-Ming W. Chiu, Using Semi-Joins to Solve Relational Queries, Journal of the ACM (JACM), v.28 n.1, p.25-40, Jan. 1981 [doi>10.1145/322234.322238]
• 7: 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]
• 8: Kaushik Chakrabarti , Surajit Chaudhuri , Venkatesh Ganti , Dong Xin, An efficient filter for approximate membership checking, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376697]
• 9: 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]
• 10: 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]
• 11: 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
• 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: Surajit Chaudhuri , Anish Das Sarma , Venkatesh Ganti , Raghav Kaushik, Leveraging aggregate constraints for deduplication, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247530]
• 14: A. M. Cohen. Unsupervised gene/protein entity normalization using automatically extracted dictionaries. In Proceedings of the BioLINK2005 Workshop 2005.
• 15: William W. Cohen , Sunita Sarawagi, Exploiting dictionaries in named entity extraction: combining semi-Markov extraction processes and data integration methods, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014065]
• 16: 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
• 17: 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]
• 18: Marios Hadjieleftheriou , Xiaohui Yu , Nick Koudas , Divesh Srivastava, Hashed samples: selectivity estimators for set similarity selection queries, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453883]
• 19: Liang Jin , Chen Li, Selectivity estimation for fuzzy string predicates in large data sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 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 , 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]
• 22: 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
• 23: Michael D. Lieberman , Jagan Sankaranarayanan , Hanan Samet, A Fast Similarity Join Algorithm Using Graphics Processing Units, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1111-1120, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497520]
• 24: Arturas Mazeika , Michael H. Böhlen , Nick Koudas , Divesh Srivastava, Estimating the selectivity of approximate string queries, ACM Transactions on Database Systems (TODS), v.32 n.2, p.12-es, June 2007 [doi>10.1145/1242524.1242529]
• 25: E. W. Myers. A sublinear algorithm for approximate keyword searching. Algorithmica 12(4/5):345--374, 1994.
• 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: Gonzalo Navarro , Ricardo Baeza-Yates , João Marcelo Azevedo Arcoverde, Matchsimile: a flexible approximate matching tool for searching proper names, Journal of the American Society for Information Science and Technology, v.54 n.1, p.3-15, January 2003 [doi>10.1002/asi.10178]
• 28: G. Navarro, R. A. Baeza-Yates, E. Sutinen, andJ. Tarhio. Indexing methods for approximate string matching. IEEE Data Eng. Bull. 24(4):19--27, 2001.
• 29: Roberto Navigli, Word sense disambiguation: A survey, ACM Computing Surveys (CSUR), v.41 n.2, p.1-69, February 2009 [doi>10.1145/1459352.1459355]
• 30: B. -W. On, N. Koudas, D. Lee, and D. Srivastava. Group linkage. In ICDE pages 496--505, 2007.
• 31: Marius Pasca, Acquisition of categorized named entities for web search, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031194]
• 32: 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]
• 33: B. S. T. Bocek, E. Hunt. Fast Similarity Search in Large Dictionaries. Technical Report ifi-2007. 02, Department of Informatics, University of Zurich, April 2007.
• 34: L. Tanabe and W. J. Wilbur. Generation of a large gene/protein lexicon by morphological pattern analysis. Journal of Bioinformatics and Computational Biology 1(4):1--16, 2004.
• 35: Yoshimasa Tsuruoka , Jun'ichi Tsujii, Improving the performance of dictionary-based approaches in protein name recognition, Journal of Biomedical Informatics, v.37 n.6, p.461-470, December 2004 [doi>10.1016/j.jbi.2004.08.003]
• 36: Esko Ukkonen, Algorithms for approximate string matching, Information and Control, v.64 n.1-3, p.100-118, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80046-2]
• 37: E. Ukkonen. Finding approximate patterns in strings. J. Algorithms 6(1):132--137, 1985.
• 38: J. Wang, Z. Li, C. Cai, and Y. Chen. Assessment of approximate string matching in a biomedical text retrieval problem. Computers in Biology and Medicine 35(8):717--724, 2005.
• 39: Chuan Xiao , Wei Wang , Xuemin Lin, Ed-Join: an efficient algorithm for similarity joins with edit distance constraints, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453957]
• 40: 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]
• 41: 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]
• 42: Justin Zobel , Philip Dart, Finding approximate matches in large lexicons, Software—Practice & Experience, v.25 n.3, p.331-345, March 1995 [doi>10.1002/spe.4380250307]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

General Terms:
Algorithms, Performance

Keywords:
approximate dictionary matching, edit distance, named entity recognition