Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Entity resolution, also known as data matching or record linkage, is the task of identifying and matching records from several databases that refer to the same entities. Traditionally, entity resolution has been applied in batch-mode and on static databases. However, many organisations are increasingly faced with the challenge of having large databases containing entities that need to be matched in real-time with a stream of query records also containing entities, such that the best matching records are retrieved. Example applications include online law enforcement and national security databases, public health surveillance and emergency response systems, financial verification systems, online retail stores, eGovernment services, and digital libraries.

A novel inverted index based approach for real-time entity resolution is presented in this paper. At build time, similarities between attribute values are computed and stored to support the fast matching of records at query time. The presented approach differs from other approaches to approximate query matching in that it allows any similarity comparison function, and any 'blocking' (encoding) function, both possibly domain specific, to be incorporated.

Experimental results on a real-world database indicate that the total size of all data structures of this novel index approach grows sub-linearly with the size of the database, and that it allows matching of query records in sub-second time, more than two orders of magnitude faster than a traditional entity resolution index approach. The interested reader is referred to the longer version of this paper [5].

REFERENCES

• 1: Akiko Aizawa , Keizo Oyama, A Fast Linkage Detection Scheme for Multi-Source Information Integration, Proceedings of the International Workshop on Challenges in Web Information Retrieval and Integration, p.30-39, April 08-09, 2005
• 2: R. Baxter, P. Christen, and T. Churches. A comparison of fast blocking methods for record linkage. In ACM SIGKDD'03 Workshop on Data Cleaning, Record Linkage and Object Consolidation, Washington DC, 2003.
• 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: Peter Christen, A Comparison of Personal Name Matching: Techniques and Practical Issues, Proceedings of the Sixth IEEE International Conference on Data Mining - Workshops, p.290-294, December 18-22, 2006 [doi>10.1109/ICDMW.2006.2]
• 5: P. Christen, R. Gayler, and D. Hawking. Similarity-aware indexing for real-time entity resolution. Technical Report TR-CS-09-01, School of Computer Science, The Australian National University, Canberra, Australia, 2009.
• 6: William W. Cohen , Jacob Richman, Learning to match and cluster large high-dimensional data sets for data integration, 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.775116]
• 7: Mauricio A. Hernández , Salvatore J. Stolfo, The merge/purge problem for large databases, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.127-138, May 22-25, 1995, San Jose, California, United States [doi>10.1145/223784.223807]
• 8: William E. Winkler, Methods for evaluating and creating data quality, Information Systems, v.29 n.7, p.531-550, October 2004 [doi>10.1016/j.is.2003.12.003]
• 9: 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.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
approximate string matching, data matching, inverted indexing, phonetic encoding, record linkage, scalability, similarity query