Learning to deduplicate

ABSTRACT

Identifying record replicas in Digital Libraries and other types of digital repositories is fundamental to improve the quality of their content and services as well as to yield eventual sharing efforts. Several deduplication strategies are available, but most of them rely on manually chosen settings to combine evidence used to identify records as being replicas. In this paper, we present the results of experiments we have carried out with a novel Machine Learning approach we have proposed for the deduplication problem. This approach, based on Genetic Programming (GP), is able to automatically generate similarity functions to identify record replicas in a given repository. The generated similarity functions properly combine and weight the best evidence available among the record fields in order to tell when two distinct records represent the same real-world entity. The results of the experiments show that our approach outperforms the baseline method by Fellegi and Sunter by more than 12% when identifying replicas in a data set containing researcher's personal data, and by more than 7%, in a data set with article citation data.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: Wolfgang Banzhaf , Frank D. Francone , Robert E. Keller , Peter Nordin, Genetic programming: an introduction: on the automatic evolution of computer programs and its applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 3: 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]
• 4: Mikhail Bilenko , Raymond J. Mooney, Adaptive duplicate detection using learnable string similarity measures, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956759]
• 5: Peter Ross , Emma Hart , David Corne, Some Observations about GA-Based Exam Timetabling, Selected papers from the Second International Conference on Practice and Theory of Automated Timetabling II, p.115-129, August 20-22, 1997
• 6: Joyce C. P. Carvalho , Altigran S. da Silva, Finding similar identities among objects from multiple web sources, Proceedings of the 5th ACM international workshop on Web information and data management, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956699.956719]
• 7: Surajit Chaudhuri , Kris Ganjam , Venkatesh Ganti , Rajeev Motwani, Robust and efficient fuzzy match for online data cleaning, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872796]
• 8: 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]
• 9: 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]
• 10: Freely Extensible Biomedical Record Linkage. http://sourceforge.net/projects/febrl.
• 11: Fellegi, I. P., and Sunter, A. B. A theory for record linkage. Journal of American Statistical Association 66, 1 (1969), 1183--1210.
• 12: Guha, S., Koudas, N., Marathe, A., and Srivastava, D. Merging the results of approximate match operations. In Proc. of VLDB (2004), pp. 636--647.
• 13: Taher H. Haveliwala , Aristides Gionis , Dan Klein , Piotr Indyk, Evaluating strategies for similarity search on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511502]
• 14: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 15: Steve Lawrence , C. Lee Giles , Kurt D. Bollacker, Autonomous citation matching, Proceedings of the third annual conference on Autonomous Agents, p.392-393, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301255]
• 16: 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 ]
• 17: Dongwon Lee , Byung-Won On , Jaewoo Kang , Sanghyun Park, Effective and scalable solutions for mixed and split citation problems in digital libraries, Proceedings of the 2nd international workshop on Information quality in information systems, June 17-17, 2005, Baltimore, Maryland [doi>10.1145/1077501.1077514]
• 18: Sheila Tejada , Craig A. Knoblock , Steven Minton, Learning object identification rules for information integration, Information Systems, v.26 n.8, p.607-633, December 2001 [doi>10.1016/S0306-4379(01)00042-4 ]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.7 Digital Libraries

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Management

Keywords:
deduplication, digital libraries, genetic programming