Projects per year
Abstract
Keys for graphs aim to uniquely identify entities represented by vertices in a graph. We propose a class of keys that are recursively defined in terms of graph patterns, and are interpreted with subgraph isomorphism. Extending conventional keys for relations and XML, these keys find applications in object identification, knowledge fusion and social network reconciliation. As an application, we study the entity matching problem that, given a graph G and a set Σ of keys, is to find all pairs of entities (vertices) in G that are identified by keys in Σ. We show that the problem is intractable, and cannot be parallelized in logarithmic rounds. Nonetheless, we provide two parallel scalable algorithms for entity matching, in MapReduce and a vertex-centric asynchronous model. Using real-life and synthetic data, we experimentally verify the effectiveness and scalability of the algorithms.
Original language | English |
---|---|
Pages (from-to) | 1590-1601 |
Number of pages | 12 |
Journal | Proceedings of the VLDB Endowment (PVLDB) |
Volume | 8 |
Issue number | 12 |
DOIs | |
Publication status | Published - Aug 2015 |
Fingerprint
Dive into the research topics of 'Keys for Graphs'. Together they form a unique fingerprint.Projects
- 2 Finished
-
VADA: Value Added Data Systems: Principles and Architecture
Libkin, L. (Principal Investigator), Buneman, P. (Co-investigator), Fan, W. (Co-investigator) & Pieris, A. (Co-investigator)
1/04/15 → 30/09/20
Project: Research
-
Querying Graph Structured Data: Principles and Techniques
Libkin, L. (Principal Investigator) & Fan, W. (Co-investigator)
1/11/13 → 31/10/16
Project: Research