Domain-independent data cleaning via analysis of entity-relationship graph

ABSTRACT

In this article, we address the problem of reference disambiguation. Specifically, we consider a situation where entities in the database are referred to using descriptions (e.g., a set of instantiated attributes). The objective of reference disambiguation is to identify the unique entity to which each description corresponds. The key difference between the approach we propose (called RelDC) and the traditional techniques is that RelDC analyzes not only object features but also inter-object relationships to improve the disambiguation quality. Our extensive experiments over two real data sets and over synthetic datasets show that analysis of relationships significantly improves quality of the result.

REFERENCES

• 1: Ananthakrishna, R., Chaudhuri, S., and Ganti, V. 2002. Eliminating fuzzy duplicates in data warehouses. In Proceedings of the VLDB Conference.
• 2: Arvind Hulgeri , Charuta Nakhe, Keyword Searching and Browsing in Databases using BANKS, Proceedings of the 18th International Conference on Data Engineering, p.431, February 26-March 01, 2002
• 3: Indrajit Bhattacharya , Lise Getoor, Iterative record linkage for cleaning and integration, Proceedings of the 9th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13, 2004, Paris, France [doi>10.1145/1008694.1008697]
• 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: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 6: Surajit Chaudhuri , Kris Ganjam , Venky Ganti , Rahul Kapoor , Vivek Narasayya , Theo Vassilakis, Data cleaning in microsoft SQL server 2005, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066287]
• 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: Zhaoqi Chen , Dmitri V. Kalashnikov , Sharad Mehrotra, Exploiting relationships for object consolidation, Proceedings of the 2nd international workshop on Information quality in information systems, June 17-17, 2005, Baltimore, Maryland [doi>10.1145/1077501.1077512]
• 9: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluating probabilistic queries over imprecise data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872823]
• 10: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Querying Imprecise Data in Moving Object Environments, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1112-1127, September 2004 [doi>10.1109/TKDE.2004.46]
• 11: Cheng, R., Prabhakar, S., and Kalashnikov, D. 2003b. Querying imprecise data in moving object environments. In Proceedings of the IEEE ICDE Conference. Bangalore, India. IEEE Computer Society Press, Los Alamitos, CA.
• 12: Christen, P., Churches, T., and Zhu, J. X. 2002. Probabilistic name and address cleaning and standardization. In Proceedings of the Australasian Data Mining Workshop.
• 13: CiteSeer 2005. http://citeseer.nj.nec.com/cs.
• 14: William W. Cohen, Integration of heterogeneous databases without common domains using queries based on textual similarity, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.201-212, June 01-04, 1998, Seattle, Washington, United States
• 15: Edith Cohen , David D. Lewis, Approximating matrix multiplication for pattern recognition tasks, Journal of Algorithms, v.30 n.2, p.211-252, Feb. 1999 [doi>10.1006/jagm.1998.0989]
• 16: William W. Cohen , Henry Kautz , David McAllester, Hardening soft information sources, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.255-259, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347141]
• 17: Cohen, W. W., Ravikumar, P., and Fienberg, S. E. 2003. A comparison of string distance metrics for name-matching tasks. In Proceedings of the IIWeb Workshop.
• 18: 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]
• 19: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 20: Luc De Raedt , Hendrik Blockeel , Luc Dehaspe , Wim Van Laer, Three companions for data mining in first order logic, Relational Data Mining, Springer-Verlag New York, Inc., New York, NY, 2001
• 21: 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]
• 22: Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014068]
• 23: Fellegi, I. and Sunter, A. 1969. A theory for record linkage. J. Amer. Stat. Assoc. 64, 328, 1183--1210.
• 24: GAMS solvers 2005. http://www.gams.com/solvers/.
• 25: Jeffrey D. Ullman , Hector Garcia-Molina , Jennifer Widom, Database Systems: The Complete Book, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 26: Getoor, L. 2001. Multi-relational data mining using probabilistic relational models: Research summary. In Proceedings of the 1st Workshop in Multi-Relational Data Mining.
• 27: Luis Gravano , Panagiotis G. Ipeirotis , H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Approximate String Joins in a Database (Almost) for Free, Proceedings of the 27th International Conference on Very Large Data Bases, p.491-500, September 11-14, 2001
• 28: 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
• 29: HomePageSearch 2005. http://hpsearch.uni-trier.de.
• 30: Jaro, M. 1989. Advances in record-linkage methodology as applied to matching the 1985 census of Tampa, Florida. J. Amer. Stat. Assoc. 84, 406.
• 31: Jaro, M. 1995. Probabilistic linkage of large public health data files. Stat. Med. 14, 5--7 (Mar.--Apr.).
• 32: 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
• 33: Kalashnikov, D. and Mehrotra. 2003. Exploiting relationships for data cleaning. UCI Tech. Rep. TR-RESCUE-03-02.
• 34: Kalashnikov, D. V. and Mehrotra, S. 2004. Learning importance of relationships for reference disambiguation. UCI Tech. Rep. TR-RESCUE-04-23.
• 35: Kalashnikov, D. V. and Mehrotra, S. 2005. Exploiting relationships for domain-independent data-cleaning. SIAM SDM (extended version), www.ics.uci.edu/~dvk/pub/sdm05.pdf.
• 36: Kalashnikov, D. V., Mehrotra, S., and Chen, Z. 2005. Exploiting relationships for domain-independent data-cleaning. In Proceedings of the SIAM International Conference on Data Mining (SIAM SDM 2005) (Newport Beach, CA).
• 37: Dmitri V. Kalashnikov , Sunil Prabhakar, Similarity Join for Low-and High-Dimensional Data, Proceedings of the Eighth International Conference on Database Systems for Advanced Applications, p.7, March 26-28, 2003
• 38: Kalashnikov, D. V. and Prabhakar, S. 2006. Fast similarity join for multi-dimensional data. Inf. Syst. J. to appear.
• 39: KDSurvey 2003. http://www.kdnuggets.com/polls/2003/data_preparation.htm.
• 40: Mong Li Lee , Wynne Hsu , Vijay Kothari, Cleaning the Spurious Links in Data, IEEE Intelligent Systems, v.19 n.2, p.28-33, March 2004 [doi>10.1109/MIS.2004.1274908]
• 41: Mong-Li Lee , Tok Wang Ling , Hongjun Lu , Yee Teng Ko, Cleansing Data for Mining and Warehousing, Proceedings of the 10th International Conference on Database and Expert Systems Applications, p.751-760, August 30-September 03, 1999
• 42: Li, X., Morie, P., and Roth, D. 2004. Identification and tracing of ambiguous names: Discriminative and generative approaches. In Proceedings of the AAAI.
• 43: Roderick J A Little , Donald B Rubin, Statistical analysis with missing data, John Wiley & Sons, Inc., New York, NY, 1986
• 44: Maletic, J. and Marcus, A. 2000. Data cleansing: Beyond integrity checking. In Proceedings of the Conference on Information Quality.
• 45: Malin, B. 2005. Unsupervised name disambiguation via social network similarity. In Proceedings of the Workshop on Link Analysis, Counterterrorism, and Security.
• 46: McCallum, A. and Wellner, B. 2003. Object consolidation by graph partitioning with a conditionally-trained distance metric. In Proceedings of the KDD Workshop on Data Cleaning, Record Linkage and Object Consolidation.
• 47: McCallum, A. and Wellner, B. 2004. Conditional models of identity uncertainty with application to noun coreference. In Proceedings of the NIPS.
• 48: 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]
• 49: Monge, A. E. and Elkan, C. 1996. The field matching problem: Algorithms and applications. In Proceedings of the ACM SIGKDD Conference. Portland, OR.
• 50: Monge, A. E. and Elkan, C. P. 1997. An efficient domain-independent algorithm for detecting approximately duplicate database records. In Proceedings of the SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery. Tucson, AZ.
• 51: Newcombe, H., Kennedy, J., Axford, S., and James, A. 1959. Automatic linkage of vital records. Science 130, 954--959.
• 52: Pasula, H., Marthi, B., Milch, B., Russell, S., and Shpitser, I. 2002. Identity uncertainty and citation matching. In Proceedings of the NIPS Conference.
• 53: Eric Sven Ristad , Peter N. Yianilos, Learning String-Edit Distance, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.5, p.522-532, May 1998 [doi>10.1109/34.682181]
• 54: 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]
• 55: Seid, D. and Mehrotra, S. 2006. Complex analytical queries over large attributed graph data. Submitted for Publication.
• 56: John Shawe-Taylor , Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, 2004
• 57: Singla, P. and Domingos, P. 2004. Multi-relational record linkage. In Proceedings of the MRDM Workshop.
• 58: Sheila Tejada , Craig A. Knoblock , Steven Minton, Learning domain-independent string transformation weights for high accuracy object identification, 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.775099]
• 59: V. S. Verykios , G. V. Moustakides , M. G. Elfeky, A Bayesian decision model for cost optimal record matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.1, p.28-40, May 2003 [doi>10.1007/s00778-002-0072-y]
• 60: Scott White , Padhraic Smyth, Algorithms for estimating relative importance in networks, 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.956782]
• 61: Wiederhold, G. 2005. The movies dataset. www-db.stanford.edu/pub/movies/doc.html.
• 62: Winkler, W. E. 1994. Advanced methods for record linkage. In Proceedings of the U.S. Bureau of Census.
• 63: Winkler, W. 1999. The state of record linkage and current research problems. In Proceedings of the U.S. Bureau of Census, TR99.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.m Miscellaneous

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.5 Heterogeneous Databases
      H.2.8 Database applications
          Subjects: Data mining
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
Connection strength, RelDC, data cleaning, entity resolution, graph analysis, reference disambiguation, relationship analysis