idMesh: graph-based disambiguation of linked data

ABSTRACT

We tackle the problem of disambiguating entities on the Web. We propose a user-driven scheme where graphs of entities -- represented by globally identifiable declarative artifacts -- self-organize in a dynamic and probabilistic manner. Our solution has the following two desirable properties: i) it lets end-users freely define associations between arbitrary entities and ii) it probabilistically infers entity relationships based on uncertain links using constraint-satisfaction mechanisms. We outline the interface between our scheme and the current data Web, and show how higher-layer applications can take advantage of our approach to enhance search and update of information relating to online entities. We describe a decentralized infrastructure supporting efficient and scalable entity disambiguation and demonstrate the practicability of our approach in a deployment over several hundreds of machines.

REFERENCES

• 1: Karl Aberer , Zoran Despotovic, Managing trust in a peer-2-peer information system, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502638]
• 2: John Allsop, Microformats: Empowering Your Markup for Web 2.0, friends of ED, 2007
• 3: Ron Bekkerman , Andrew McCallum, Disambiguating Web appearances of people in a social network, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060813]
• 4: G. Bianconi and M. Marsili. Loops of any size and hamilton cycles in random scale-free networks. Journal of Statistical Mechanics: Theory and Experiments, P06005, 2005.
• 5: Paolo Bouquet , Heiko Stoermer , Claudia Niederee , Antonio Maña, Entity Name System: The Back-Bone of an Open and Scalable Web of Data, Proceedings of the 2008 IEEE International Conference on Semantic Computing, p.554-561, August 04-07, 2008 [doi>10.1109/ICSC.2008.37]
• 6: D. Brickley and L. Miller. FOAF Vocabulary Specification 0.91. http://xmlns.com/foaf/spec/.
• 7: T. Celic, M. Mullenweg, and E. Meyer. Xhtml Friends Network Relationships Meta Data Profile 1.1. http://gmpg.org/xfn/11.
• 8: H. Choi, S. Kruk, S. Grzonkowski, K. Stankiewicz, B. Davis, and J. Breslin. Trust Models for Community-Aware Identity Management. Identity, Reference, and the Web Workshop at the World Wide Web Conference (WWW), 2006.
• 9: Philippe Cudre-Mauroux, Emergent Semantics, EPFL Press, 2008
• 10: Philippe Cudre-Mauroux , Karl Aberer , Andras Feher, Probabilistic Message Passing in Peer Data Management Systems, Proceedings of the 22nd International Conference on Data Engineering, p.41, April 03-07, 2006 [doi>10.1109/ICDE.2006.118]
• 11: Philippe Cudre-Mauroux , Suchit Agarwal , Karl Aberer, GridVine: An Infrastructure for Peer Information Management, IEEE Internet Computing, v.11 n.5, p.36-44, September 2007 [doi>10.1109/MIC.2007.108]
• 12: 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]
• 13: R. Hoelzer, B. Malin, and L. Sweeney. Email Alias Detection Using Social Network Analysis. In International Workshop on Link Analysis (LinkKDD), 2005.
• 14: A. Hogan, A. Harth, and S. Decker. Performing object consolidation on the semantic web data graph. In I³: Identity, Identifiers, Identification, Entity-Centric Approaches to Information and Knowledge Management on the Web workshop at the World Wide Web conference (WWW), 2007.
• 15: Ekaterini Ioannou , Claudia Niederée , Wolfgang Nejdl, Probabilistic Entity Linkage for Heterogeneous Information Spaces, Proceedings of the 20th international conference on Advanced Information Systems Engineering, June 16-20, 2008 [doi>10.1007/978-3-540-69534-9_41]
• 16: A. Jaffri, H. Glaser, and I. Millard. URI Disambiguation in the Context of Linked Data. In Workshop on Linked Data on the Web (LDOW), 2008.
• 17: Nick Koudas , Sunita Sarawagi , Divesh Srivastava, Record linkage: similarity measures and algorithms, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142599]
• 18: Nick Koudas , Divesh Srivastava, Approximate joins: concepts and techniques, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 19: F. Kschischang, B. Frey, and H.-A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2), 2001.
• 20: Einat Minkov , William W. Cohen , Andrew Y. Ng, Contextual search and name disambiguation in email using graphs, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148179]
• 21: K. M. Murphy, Y. Weiss, and M. I. Jordan. Loopy belief propagation for approximate inference: An empirical study. In Uncertainty in Artificial Intelligence (UAI), 1999.
• 22: Byung-Won On , Ergin Elmacioglu , Dongwon Lee , Jaewoo Kang , Jian Pei, Improving Grouped-Entity Resolution Using Quasi-Cliques, Proceedings of the Sixth International Conference on Data Mining, p.1008-1015, December 18-22, 2006 [doi>10.1109/ICDM.2006.85]
• 23: Y. Raimond, C. Sutton, and M. Sandler. Automatic Interlinking of Music Datasets. In International Workshop on Linked Data on the Web (LDOW), 2008.
• 24: W. Roush. People-powered search. MIT Technology Review, May--June, 2007. https://www.technologyreview.com/Infotech/18655/.
• 25: G. Shafer. A Mathematical Theory of Evidence. Princeton, NJ: Princeton Univ. Press, 1976.
• 26: W. Shen, X. Li, and A. Doan. Constraint-based entity matching. In National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference (AAAI), 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.m MISCELLANEOUS

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.12 Interoperability
            Subjects: Data mapping

General Terms:
Algorithms, Design

Keywords:
emergent semantics, entity disambiguation, linked data, peer data management