Keys for Graphs

Summary: Introduces recursively defined graph keys interpreted via subgraph isomorphism, generalizing relational/XML keys for entity identification and reconciliation. Despite intractable, non-logarithmically parallelizable matching, presents scalable MapReduce and asynchronous vertex-centric algorithms. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h309575b8076baf1e
Venue: VLDB
Year: 2015
Pagerank: 7.436464e-05
Overall Rank: 3,317 | 77.70%
DOI: 10.14778/2824032.2824056

Incoming Non-self Citations Over Time

Authors

1. Wenfei Fan (Beihang University; University of Edinburgh)
2. Zhe Fan (Hong Kong Baptist University)
3. Chao Tian (Beihang University; University of Edinburgh)
4. Xin Luna Dong (Google)

BibTeX Citation

@article{fan_vldb15,
        title = {{Keys for Graphs}},
        author = {Fan, Wenfei and Fan, Zhe and Tian, Chao and Dong, Xin Luna},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {12},
        pages = {1590--1603},
        doi = {10.14778/2824032.2824056},
        url = {https://doi.org/10.14778/2824032.2824056},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,364	Dependencies for Graphs	2017	PODS	8.5665938e-05
2,831	PG-Keys: Keys for Property Graphs	2021	SIGMOD	7.9602632e-05
3,026	Functional Dependencies for Graphs	2016	SIGMOD	7.7387829e-05
3,767	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	7.0315534e-05
5,513	Big Graphs: Challenges and Opportunities	2022	VLDB	6.0986544e-05
6,525	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.756805e-05
7,226	Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs)	2019	VLDB	5.5810344e-05
7,342	Discovering Association Rules from Big Graphs	2022	VLDB	5.5480127e-05
8,293	Capturing Associations in Graphs	2020	VLDB	5.3612871e-05
8,398	Deducing Certain Fixes to Graphs	2019	VLDB	5.3399392e-05
8,590	Ontology-based Entity Matching in Attributed Graphs	2019	VLDB	5.3071244e-05
9,806	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.1257999e-05
10,720	Structural Normalization of Property Graphs	2026	VLDB	4.9793485e-05
11,186	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	4.9793485e-05
11,966	GRIP: Constraint-based Explanation of Missing Answers for Graph Queries	2021	SIGMOD	4.9793485e-05
12,210	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
22	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00055962491
230	Reference Reconciliation in Complex Information Spaces	2005	SIGMOD	0.00023871933
384	HaLoop: Efficient Iterative Data Processing on Large Clusters	2010	VLDB	0.0001948031
443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018197688
490	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017438618
623	Entity Resolution: Theory, Practice & Open Challenges	2012	VLDB	0.00015483844
1,548	Distributed SociaLite: A Datalog-Based Language for Large-Scale Graph Analysis	2013	VLDB	0.00010290306
2,070	Dedoop: Efficient Deduplication with Hadoop	2012	VLDB	9.0876046e-05
2,392	From Data Fusion to Knowledge Fusion	2014	VLDB	8.5332502e-05
3,273	Large-Scale Collective Entity Matching	2011	VLDB	7.471033e-05
3,416	An efficient reconciliation algorithm for social networks	2014	VLDB	7.3224351e-05
5,426	Active Knowledge: Dynamically Enriching RDF Knowledge Bases by Web Services	2010	SIGMOD	6.1342038e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,583	Event Pattern Matching over Graph Streams	2015	VLDB
2	657	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD
3	1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB
4	10,746	gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs	2026	VLDB
5	10,740	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB
6	1,900	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD
7	12,059	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD
8	1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB
9	443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
10	8,590	Ontology-based Entity Matching in Attributed Graphs	2019	VLDB