Edinburgh Research Explorer

Keys for Graphs

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions



  • Download as Adobe PDF

    Accepted author manuscript, 366 KB, PDF document

    Licence: Creative Commons: Attribution-NonCommercial-NoDerivatives (CC BY-NC-ND)

Original languageEnglish
Pages (from-to)1590-1601
Number of pages12
JournalProceedings of the VLDB Endowment (PVLDB)
Issue number12
Publication statusPublished - Aug 2015


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.

Download statistics

No data available

ID: 24539781