Learning to match and cluster large high-dimensional data sets for data integration

ABSTRACT

Part of the process of data integration is determining which sets of identifiers refer to the same real-world entities. In integrating databases found on the Web or obtained by using information extraction methods, it is often possible to solve this problem by exploiting similarities in the textual names used for objects in different databases. In this paper we describe techniques for clustering and matching identifier names that are both scalable and adaptive, in the sense that they can be trained to obtain better performance in a particular domain. An experimental evaluation on a number of sample datasets shows that the adaptive method sometimes performs much better than either of two non-adaptive baseline systems, and is nearly always competitive with the best baseline system.

REFERENCES

• 1: William W. Cohen, Reasoning about Textual Similarity in a Web-Based Information Access System, Autonomous Agents and Multi-Agent Systems, v.2 n.1, p.65-86, March 1999 [doi>10.1023/A:1010031208520]
• 2: William W. Cohen, Data integration using similarity joins and a word-based information representation language, ACM Transactions on Information Systems (TOIS), v.18 n.3, p.288-321, July 2000 [doi>10.1145/352595.352598]
• 3: William W. Cohen, WHIRL: a word-based information representation language, Artificial Intelligence, v.118 n.1-2, p.163-196, April 2000 [doi>10.1016/S0004-3702(99)00102-2]
• 4: William W. Cohen and Jacob Richman. Learning to match and cluster entity names. In Proceedings of the ACM SIGIR-2001 Workshop on Mathematical/Formal Methods in Information Retrieval, New Orleans, LA, 2001.
• 5: William W. Cohen, Robert E. Schapire, and Yoram Singer. Learning to order things. Journal of Artificial Intelligence Research, 10:243--270, 1999.
• 6: Mark Craven , Dan DiPasquo , Dayne Freitag , Andrew McCallum , Tom Mitchell , Kamal Nigam , Seán Slattery, Learning to extract symbolic knowledge from the World Wide Web, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.509-516, July 1998, Madison, Wisconsin, United States
• 7: I. P. Felligi and A. B. Sunter. A theory for record linkage. Journal of the American Statistical Society, 64:1183--1210, 1969.
• 8: Helena Galhardas , Daniela Florescu , Dennis Shasha , Eric Simon, AJAX: an extensible data cleaning tool, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.590, May 15-18, 2000, Dallas, Texas, United States
• 9: 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
• 10: B. Kilss and W. Alvey. Record linkage techniques--1985. Statistics of Income Division, Internal Revenue Service Publication 1299-2-96. Available from http://www.bts.gov/fcsm/methodology/, 1985.
• 11: Steve Lawrence , C. Lee Giles , Kurt Bollacker, Digital Libraries and Autonomous Citation Indexing, Computer, v.32 n.6, p.67-71, June 1999 [doi>10.1109/2.769447]
• 12: Andrew Kachites McCallum , Kamal Nigam , Jason Rennie , Kristie Seymore, Automating the Construction of Internet Portals with Machine Learning, Information Retrieval, v.3 n.2, p.127-163, July 2000 [doi>10.1023/A:1009953814988]
• 13: Andrew McCallum , Kamal Nigam , Lyle H. Ungar, Efficient clustering of high-dimensional data sets with application to reference matching, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.169-178, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347123]
• 14: A. Monge and C. Elkan. The field-matching problem: algorithm and applications. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, August 1996.
• 15: H. B. Newcombe, J. M. Kennedy, S. J. Axford, and A. P. James. Automatic linkage of vital records. Science, 130:954--959, 1959.
• 16: Kamal Nigam, John Lafferty, and Andrew McCallum. Using maximum entropy for text classification. In Proceedings of Machine Learning for Information Filtering Workshop, IJCAI '99, Stockholm, Sweden, 1999.
• 17: H.A. Baler Saip and C.L. Lucchesi. Matching algorithm, for bipartite graph. Technical Report DCC-03/93, Departamento de Cincia da Computao, Universidade Estudal de Campinas, 1993.
• 18: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 19: W. E. Winkler. Improved decision rules in the Felligi-Sunter model of record linkage. Statistics of Income Division, Internal Revenue Service Publication RR93/12. Available from http://www.census.gov/srd/www/byname.html, 1993.
• 20: W. E. Winkler. The state of record linkage and current research problems. Statistics of Income Division, Internal Revenue Service Publication R99/04. Available from http://www.census.gov/srd/www/byname.html, 1999.
• 21: William E. Winkler. Matching and record linkage. In Business Survey methods. Wiley, 1995.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.1 Application Packages
          Subjects: Database processing

General Terms:
Algorithms, Measurement, Performance

Keywords:
clustering, large datasets, learning, text mining