Structure-based inference of xml similarity for fuzzy duplicate detection

ABSTRACT

Fuzzy duplicate detection aims at identifying multiple representations of real-world objects stored in a data source, and is a task of critical practical relevance in data cleaning, data mining, or data integration. It has a long history for relational data stored in a single table (or in multiple tables with equal schema). Algorithms for fuzzy duplicate detection in more complex structures, e.g., hierarchies of a data warehouse, XML data, or graph data have only recently emerged. These algorithms use similarity measures that consider the duplicate status of their direct neighbors, e.g., children in hierarchical data, to improve duplicate detection effectiveness. In this paper, we propose a novel method for fuzzy duplicate detection in hierarchical and semi-structured XML data. Unlike previous approaches, it not only considers the duplicate status of children, but rather the probability of descendants being duplicates. Probabilities are computed efficiently using a Bayesian network. Experiments show the proposed algorithm is able to maintain high precision and recall values, even when dealing with data containing a high amount of errors and missing information. Our proposal is also able to outperform a state-of-the-art duplicate detection system on three different XML databases.

REFERENCES

• 1: S. Acid, L. M. de Campos, J. M. Fernández-Luna, and J. F. Huete. An information retrieval model based on simple bayesian networks. International Journal of Intelligent Systems, 18(2):251--265, Jan. 2003.
• 2: Rohit Ananthakrishna , Surajit Chaudhuri , Venkatesh Ganti, Eliminating fuzzy duplicates in data warehouses, Proceedings of the 28th international conference on Very Large Data Bases, p.586-597, August 20-23, 2002, Hong Kong, China
• 3: Indrajit Bhattacharya , Lise Getoor , Louis Licamele, Query-time entity resolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150463]
• 4: I. Bhattacharya and L. Getoor. A latent dirichlet model for unsupervised entity resolution. In Conference on Data Mining (SDM), Bethesda, MD, 2006.
• 5: 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]
• 6: Surajit Chaudhuri , Venkatesh Ganti , Rajeev Motwani, Robust Identification of Fuzzy Duplicates, Proceedings of the 21st International Conference on Data Engineering, p.865-876, April 05-08, 2005 [doi>10.1109/ICDE.2005.125]
• 7: 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]
• 8: Xin Dong , Alon Halevy , Jayant Madhavan, Reference reconciliation in complex information spaces, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066168]
• 9: Susan Dumais , John Platt , David Heckerman , Mehran Sahami, Inductive learning algorithms and representations for text categorization, Proceedings of the seventh international conference on Information and knowledge management, p.148-155, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288651]
• 10: I. P. Fellegi and A. B. Sunter. A theory for record linkage. Journal of the American Statistical Association, 1969.
• 11: David Haines , W. Bruce Croft, Relevance feedback and inference networks, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.2-11, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160689]
• 12: 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
• 13: Liang Jin , Chen Li , Sharad Mehrotra, Efficient Record Linkage in Large Data Sets, Proceedings of the Eighth International Conference on Database Systems for Advanced Applications, p.137, March 26-28, 2003
• 14: Dmitri V. Kalashnikov , Sharad Mehrotra, Domain-independent data cleaning via analysis of entity-relationship graph, ACM Transactions on Database Systems (TODS), v.31 n.2, p.716-767, June 2006 [doi>10.1145/1138394.1138401]
• 15: D. Milano, M. Scannapieco, and T. Catarci. Structure aware xml object identification. In VLDB Workshop on Clean Databases (CleanDB), Seoul, Korea, 2006.
• 16: A. E. Monge and C. P. Elkan. An efficient domain-independent algorithm for detecting approximately duplicate database records. In SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD), Tucson, AZ, 1997.
• 17: H. Newcombe, J. Kennedy, S. Axford, and A. James. Automatic linkage of vital records. Science 130, (3381):954--959, 1959.
• 18: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 19: S. Puhlmann, M. Weis, and F. Naumann. Xml duplicate detection using sorted neigborhoods. In Conference on Extending Database Technology (EDBT), pages 773--791, Munich, Germany, 2006.
• 20: E. Rahm and H. H. Do. Data cleaning: Problems and current approaches. IEEE Data Engineering Bulletin, 23:3--13, 2000.
• 21: Berthier A. N. Ribeiro , Richard Muntz, A belief network model for IR, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.253-260, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243272]
• 22: Sunita Sarawagi , Anuradha Bhamidipaty, Interactive deduplication using active learning, 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.775087]
• 23: P. Singla and P. Domingos. Object identification with attribute-mediated dependences. In Conference on Principals and Practice of Knowledge Discovery in Databases (PKDD), pages 297--308, Porto, Portugal, 2005.
• 24: H. Turtle , W. B. Croft, Inference networks for document retrieval, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.1-24, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98006]
• 25: Melanie Weis , Felix Naumann, Detecting duplicate objects in XML documents, Proceedings of the 2004 international workshop on Information quality in information systems, June 18, 2004, Paris, France [doi>10.1145/1012453.1012456]
• 26: Melanie Weis , Felix Naumann, DogmatiX tracks down duplicates in XML, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066207]
• 27: Melanie Weis , Felix Naumann, Detecting Duplicates in Complex XML Data, Proceedings of the 22nd International Conference on Data Engineering, p.109, April 03-07, 2006 [doi>10.1109/ICDE.2006.49]
• 28: W. E. Winkler. Overview of record linkage and current research directions. Technical report, U. S. Bureau of the Census, 2006.
• 29: Xiaoxin Yin , Jiawei Han , Philip S. Yu, LinkClus: efficient clustering via heterogeneous semantic links, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.5 Heterogeneous Databases

General Terms:
Algorithms, Experimentation, Standardization

Keywords:
bayesian networks, duplicate detection, xml