Relational clustering for multi-type entity resolution

ABSTRACT

In many applications, there are a variety of ways of referring to the same underlying entity. Given a collection of references to entities, we would like to determine the set of true underlying entities and map the references to these entities. The references may be to entities of different types and more than one type of entity may need to be resolved at the same time. We propose similarity measures for clustering references taking into account the different relations that are observed among the typed references. We pose typed entity resolution in relational data as a clustering problem and present experimental results on real data showing improvements over attribute-based models when relations are leveraged.

REFERENCES

• 1: R. Ananthakrishna, S. Chaudhuri, and V. Ganti. Eliminating fuzzy duplicates in data warehouses. In VLDB, 2002.
• 2: P. Berkhin. Survey of clustering data mining techniques. Technical report, Accrue Software, 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: I. Bhattacharya and L. Getoor. A latent dirichlet model for entity resolution. Technical report, University of Maryland, College Park, 2005.
• 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 , 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]
• 7: W. W. Cohen, P. Ravikumar, and S. E. Fienberg. A comparison of string distance metrics for name-matching tasks. In IJCAI-2003 Workshop on Information Integration on the Web, 2003.
• 8: 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]
• 9: 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]
• 10: W. Emde and D. Wettschereck. Relational instance based learning. In L. Saitta, editor, Proceedings of The 13th International Conference on Machine Learning, pages 122 -- 130. Morgan Kaufmann Publishers, 1996.
• 11: I. P. Fellegi and A. B. Sunter. A theory for record linkage. Journal of the American Statistical Association, 64:1183--1210, 1969.
• 12: C. Lee Giles , Kurt D. Bollacker , Steve Lawrence, CiteSeer: an automatic citation indexing system, Proceedings of the third ACM conference on Digital libraries, p.89-98, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276685]
• 13: 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
• 14: D. V. Kalashnikov, S. Mehrotra, and Z. Chen. Exploiting relationships for domain-independent data cleaning. In SIAM SDM, Newport Beach, CA, USA, April 21--23 2005.
• 15: Xin Li , Paul Morie , Dan Roth, Semantic integration in text: from ambiguous names to identifiable entities, AI Magazine, v.26 n.1, p.45-58, March 2005
• 16: A. McCallum and B. Wellner. Conditional models of identity uncertainty with application to noun coreference. In NIPS, 2004.
• 17: 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]
• 18: B. Milch, B. Marthi, D. Sontag, S. Russell, D. L. Ong, and A. Kolobov. Blog: Probabilistic models with unknown objects. In IJCAI, 2005.
• 19: A. E. Monge and C. P. Elkan. The field matching problem: Algorithms and applications. In KDD, 1996.
• 20: A. E. Monge and C. P. Elkan. An efficient domain-independent algorithm for detecting approximately duplicate database records. In DMKD, 1997.
• 21: Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001 [doi>10.1145/375360.375365]
• 22: J. Neville, M. Adler, and D. Jensen. Clustering relational data using attribute and link information. In Text Mining and Link Analysis Workshop, IJCAI, 2003.
• 23: Parag and P. Domingos. Multi-relational record linkage. In KDD Workshop on Multi-Relational Data Mining, 2004.
• 24: H. Pasula, B. Marthi, B. Milch, S. Russell, and I. Shpitser. Identity uncertainty and citation matching. In NIPS, 2003.
• 25: Pradeep Ravikumar , William W. Cohen, A hierarchical graphical model for record linkage, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.454-461, July 07-11, 2004, Banff, Canada
• 26: 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]
• 27: 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]
• 28: 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]
• 29: W. E. Winkler. The state of record linkage and current research problems. Technical report, U.S. Census Bureau, 1999.
• 30: W. E. Winkler. Methods for record linkage and Bayesian networks. Technical report, U.S. Census Bureau, 2002.