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.432944e-05
Overall Rank: 3,317 | 77.71%
DOI: 10.14778/2824032.2824056
PDF: Download (CC BY-NC-ND 3.0)

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,365	Dependencies for Graphs	2017	PODS	8.5625389e-05
2,831	PG-Keys: Keys for Property Graphs	2021	SIGMOD	7.9564949e-05
3,027	Functional Dependencies for Graphs	2016	SIGMOD	7.7351194e-05
3,769	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	7.0282248e-05
5,516	Big Graphs: Challenges and Opportunities	2022	VLDB	6.0957673e-05
6,528	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.7540798e-05
7,228	Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs)	2019	VLDB	5.5783924e-05
7,345	Discovering Association Rules from Big Graphs	2022	VLDB	5.5453863e-05
8,299	Capturing Associations in Graphs	2020	VLDB	5.3587491e-05
8,403	Deducing Certain Fixes to Graphs	2019	VLDB	5.3374114e-05
8,597	Ontology-based Entity Matching in Attributed Graphs	2019	VLDB	5.3046172e-05
9,813	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.1233734e-05
10,730	Structural Normalization of Property Graphs	2026	VLDB	4.9769913e-05
11,195	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	4.9769913e-05
11,972	GRIP: Constraint-based Explanation of Missing Answers for Graph Queries	2021	SIGMOD	4.9769913e-05
12,216	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	4.9769913e-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.00055938421
230	Reference Reconciliation in Complex Information Spaces	2005	SIGMOD	0.00023861741
384	HaLoop: Efficient Iterative Data Processing on Large Clusters	2010	VLDB	0.00019471648
443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018190518
489	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017440023
623	Entity Resolution: Theory, Practice & Open Challenges	2012	VLDB	0.00015477107
1,550	Distributed SociaLite: A Datalog-Based Language for Large-Scale Graph Analysis	2013	VLDB	0.00010285521
2,072	Dedoop: Efficient Deduplication with Hadoop	2012	VLDB	9.0834235e-05
2,394	From Data Fusion to Knowledge Fusion	2014	VLDB	8.529467e-05
3,274	Large-Scale Collective Entity Matching	2011	VLDB	7.4675244e-05
3,416	An efficient reconciliation algorithm for social networks	2014	VLDB	7.3189687e-05
5,430	Active Knowledge: Dynamically Enriching RDF Knowledge Bases by Web Services	2010	SIGMOD	6.1313e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,585	Event Pattern Matching over Graph Streams	2015	VLDB
2	659	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,756	gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs	2026	VLDB
5	10,750	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB
6	1,901	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD
7	12,065	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD
8	1,150	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB
9	443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
10	8,597	Ontology-based Entity Matching in Attributed Graphs	2019	VLDB