Keys for Graphs

Wenfei Fan, Zhe Fan, Chao Tian, Xin Luna Dong

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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 languageEnglish
Pages (from-to)1590-1601
Number of pages12
JournalProceedings of the VLDB Endowment (PVLDB)
Issue number12
Publication statusPublished - Aug 2015


Dive into the research topics of 'Keys for Graphs'. Together they form a unique fingerprint.

Cite this