Scaling up duplicate detection in graph data

ABSTRACT

Duplicate detection determines different representations of real-world objects in a database. Recent research has considered the use of relationships among object representations to improve duplicate detection. In the general case where relationships form a graph, research has mainly focused on duplicate detection quality/effectiveness. Scalability has been neglected so far, even though it is crucial for large real-world duplicate detection tasks.

We scale up duplicate detection in graph data (DDG) to large amounts of data using the support of a relational database system. We first generalize the process of DDG and then present how to scale DDG in space (amount of data processed with limited main memory) and in time. Finally, we explore how complex similarity computation can be performed efficiently. Experiments on data an order of magnitude larger than data considered so far in DDG clearly show that our methods scale to large amounts of data.

REFERENCES

• 1: Indrajit Bhattacharya , Lise Getoor, Collective entity resolution in relational data, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.5-es, March 2007 [doi>10.1145/1217299.1217304]
• 2: 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]
• 3: Ahmed K. Elmagarmid , Panagiotis G. Ipeirotis , Vassilios S. Verykios, Duplicate Record Detection: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.19 n.1, p.1-16, January 2007 [doi>10.1109/TKDE.2007.9]
• 4: 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
• 5: 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]
• 6: P. Singla and P. Domingos. Object identification with attribute-mediated dependences. In PKDD Conference, Porto, Portugal, 2005.
• 7: M. Weis and F. Naumann. Industry-scale duplicate detection. In VLDB Conference, Auckland, New Zealand, 2008.
• 8: M. Weis and F. Naumann. Space and time scalability of duplicate detection in graph data. Technical Report 25, Hasso-Plattner-Institut, 2008.
• 9: 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.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Algorithms, Performance

Keywords:
data quality, duplicate detection, entity resolution, scalability