2008 InteractiveEntResInRelData

Jump to: navigation, search

Subject Headings: Interactive Entity Record Deduplication System, D-Dupe System, Information Visualization, Visual Analytics.


Cited By



Databases often contain uncertain and imprecise references to real-world entities. Entity resolution, which is the process of reconciling multiple references to underlying real-world entities, is an important data cleaning process required before accurate visualization or analysis of the data is possible. In many cases, in addition to noisy data describing entities, there is data describing the relationships among the entities. This relational data is important during the entity resolution process; it is useful both for the algorithms that determine likely database references to be resolved and for visual analytic tools that support the entity resolution process. In this paper, we introduce a novel user interface, D-Dupe, for interactive entity resolution in relational data. D-Dupe effectively combines relational entity resolution algorithms with a novel network visualization that enables users to make use of an entity’s relational context for making resolution decisions. We describe resolution strategies based on pairs or sets of references and show appropriate visualizations for each. Since resolution decisions often are interdependent, D-Dupe facilitates understanding this complex process through animations that highlight combined inferences and a history mechanism that allows users to inspect chains of resolution decisions. An empirical study with 12 users confirmed the benefits of the relational context visualization on the performance of entity resolution tasks in relational data in terms of time as well as users’ confidence and satisfaction.


  • [1] Alvaro E. Monge and C. Elkan, “The Field Matching Problem: Algorithms and Applications,” Proceedings of ACM Int’l Conference Knowledge Discovery and Data Mining (SIGKDD), 1996.
  • [2] An Atlas of Cyberspace, www.cybergeography.org/atlas, 2008.

[3] B. Bederson, J. Grosjean, and J. Meyer, “Toolkit Design for Interactive Structured Graphics,” IEEE Trans. Software Eng., vol. 30, no. 8, pp. 535-546, Aug. 2004. [4] B. Shneiderman and A. Aris, “Network Visualization by Semantic Substrates,” IEEE Trans. Visualization and Computer Graphics, vol. 12, no. 5, pp. 733-740, Sept./Oct. 2006. [5] D. Kalashnikov, S. Mehrotra, and Z. Chen, “Exploiting Relationships for Domain-Independent Data Cleaning,” Proceedings of SIAM Int’l Conf. Data Mining (SIAM SDM), 2005. [6] E. Adar, “Guess: A Language and Interface for Graph Exploration,” Proc. Conference Human Factors in Computing Systems (CHI ’06), pp. 791-800, 2006. [7] Erhard Rahm and P. Bernstein, “A Survey of Approaches to Automatic Schema Matching,” The VLDB J., vol. 10, no. 4, 2001. [8] E.S. Ristad and P.N. Yianilos, “Learning String-Edit Distance,” IEEE Trans. Pattern Analysis and Machine Intelligence]], vol. 20, no. 5, pp. 522-532, May 1998. [9] G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999. [10] Gonzalo Navarro, “A Guided Tour to Approximate String Matching,” ACM Computing Surveys, vol. 33, no. 1, pp. 31-88, 2001. [11] G.E. Krasner and S.T. Pope, “A Cookbook for Using the Model- View-Controller User Interface Paradigm in Smalltalk-80,” J. Object-Oriented Programming, vol. 1, no. 3, pp. 26-49, 1988. [12] H. Kang and B. Shneiderman, “Exploring Personal Media: A Spatial Interface Supporting User-Defined Semantic Regions,” J. Visual Language and Computing, vol. 17, no. 3, pp. 254-283, 2006. [13] H. Kang, Lise Getoor, and L. Singh, “Visual Analysis of Dynamic Group Membership in Temporal Social Networks,” SIGKDD Explorations: Special Issue on Visual Analytics, vol. 9, no. 2, pp. 13-21, 2007. [14] H. Kang, V. Sehgal, and Lise Getoor, “GeoDDupe: A Novel Interface for Interactive Entity Resolution in GeoSpatial Data,” Proceedings of Int’l Conf. Information Visualisation (IV ’07), pp. 489-496, 2007. [15] I. Bhattacharya and Lise Getoor, “Collective Entity Resolution in Relational Data,” ACM Trans. Knowledge Discovery from Data (TKDD ’07), vol. 1, no. 1, 2007. [16] I. Bhattacharya and Lise Getoor, “Entity Resolution in Graphs,” Mining Graph Data, L.B. Holder and D.J. Cook, eds., Wiley, 2006. [17] I. Bhattacharya and Lise Getoor, “Iterative Record Linkage for Cleaning and Integration,” Proceedings of ACM SIGMOD Workshop Data Mining and Knowledge Discovery (DMKD ’04), pp. 11-18, 2004. [18] I. Herman, G. Melanc¸on, and M.S. Marshall, “Graph Visualization and Navigation in Information Visualization: A Survey,” IEEE Trans. Visualization and Computer Graphics, vol. 6, no. 1, pp. 24-43, Jan.-Nar, 2000.

  • [19] J. Heer, S.K. Card, and J.A. Landay, “Prefuse: A Toolkit for Interactive Information Visualization,” Proceedings of Conference Human Factors in Computing Systems (CHI ’05), pp. 421-430, 2005.
  • [20] J. O’Madadhain, D. Fisher, Padhraic Smyth, S. White, and Y.B. Boey, “Analysis and Visualization of Network Data Using JUNG,” J. Statistical Software, 2005.
  • [21] L.C. Freeman, “Visualizing Social Networks,” J. Social Structure, vol. 1, no. 1, 2000.

[22] L. Freeman, The Development of Social Network Analysis: A Study in the Sociology of Science. Empirical Press, 2004. [23] M. Baur, M. Benkert, U. Brandes, S. Cornelsen, M. Gaertler, B. Ko¨ pf, J. Lerner, and D. Wagner, “Visone Software for Visual Social Network Analysis,” Graph Drawing Software, P. Mutzel, M. Ju¨ nger, and S. Leipert, eds., pp. 463-464, Springer, 2002. [24] Mikhail Bilenko, B. Kamath, and R.J. Mooney, “Adaptive Blocking: Learning to Scale Up Record Linkage,” Proceedings of Int’l Conference Data Mining (ICDM ’06), pp. 87-96, 2006.

  • [25] M. Bilenko and R.J. Mooney, “Adaptive Duplicate Detection

Using Learnable String Similarity Measures,” Proceedings of ACM SIGKDD Int’l Conference Knowledge Discovery and Data Mining (KDD ’03), pp. 39-48, 2003. [26] Mikhail Bilenko, Raymond Mooney W. Cohen, P. Ravikumar, and S. Fienberg, “Adaptive Name Matching in Information Integration,” IEEE Intelligent Systems, vol. 18, no. 5, pp. 16-23, Sept./Oct. 2003. [27] M. Bilgic, L. Licamele, Lise Getoor, and B. Shneiderman, “D-Dupe: An Interactive Tool for Entity Resolution in Social Networks,” Proc. IEEE Symp. Visual Analytics Science and Technology (VAST ’06), pp. 43-50, 2006. [28] Netminer II: Social Network Mining Software, http://www.netminer. com/NetMiner/home 01.jsp, 2008. [29] P. Singla and Pedro Domingos, “Multi-Relational Record Linkage,” Proc. ACM SIGKDD Workshop Multi-Relational Data Mining (MRDM), 2004. [30] R. Ananthakrishna, S. Chaudhuri, and Venkatesh Ganti, “Eliminating Fuzzy Duplicates in Data Warehouses,” Proceedings of Int’l Conference Very Large Databases (VLDB), 2002. [31] S. Chaudhuri, K. Ganjam, Venkatesh Ganti, and Rajeev Motwani, “Robust and Efficient Fuzzy Match for Online Data Cleaning,” Proceedings of ACM SIGMOD, 2003.

  • [32] Sunita Sarawagi and A. Bhamidipaty, “Interactive Deduplication Using Active Learning,” Proceedings of Eighth ACM SIGKDD Int’l Conference Knowledge Discovery and Data Mining (KDD ’02), pp. 269-278, 2002.
  • [33] Stanley Wasserman and K. Faust, Social Network Analysis: Methods and Applications. Cambridge Univ. Press, 1994.
  • [34] S. Tejada, C. Knoblock, and S. Minton, “Learning Object Identification Rules for Information Integration,” Information Systems J., vol. 26, no. 8, pp. 635-656, 2001.
  • [35] SimMetrics: Open Source Similarity Measure Library, http://www.dcs.shef.ac.uk/~sam/simmetrics.html, 2007.
  • [36] T. Dasu and T. Johnson, Exploratory Data Mining and Data Cleaning. John Wiley and Sons, 2003.
  • [37] U. Brandes, T. Raab, and D. Wagner, “Exploratory Network Visualization: Simultaneous Display of Actor Status and Connections,” J. Social Structure, vol. 2, no. 4, 2001.

[38] V. Raman and J. Hellerstein, “Potter’s Wheel: An Interactive Data Cleaning System,” Proceedings of Int’l Conference Very Large Databases (VLDB ’01), pp. 381-390, 2001. [39] Visual Complexity, http://www.visualcomplexity.com, 2007. [40] W.W. Cohen, P. Ravikumar, and S.E. Fienberg, “A Comparison of String Distance Metrics for Name-Matching Tasks,” Proceedings of IJCAI Workshop Information Integration on the Web (IIWeb ’03), pp. 73-78, 2003.

  • [41] X. Dong, A. Halevy, and J. Madhavan, “Reference Reconciliation in Complex Information Spaces,” Proceedings of ACM SIGMOD, 2005.,

 AuthorvolumeDate ValuetitletypejournaltitleUrldoinoteyear
2008 InteractiveEntResInRelDataHyunmo Kang
Lise Getoor
Ben Shneiderman
Mustafa Bilgic
Louis Licamele
Interactive Entity Resolution in Relational Data: A Visual Analytic Tool and Its EvaluationIEEE Transactions on Visualization and Computer Graphicshttp://linqs.cs.umd.edu/basilic/web/Publications/2008/kang:tvcg08/2008