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: 11224
Venue: VLDB
Year: 2015
Pagerank: 7.5963955e-05
Overall Rank: 3,251 | 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,324	Dependencies for Graphs	2017	PODS	8.7506505e-05
2,861	PG-Keys: Keys for Property Graphs	2021	SIGMOD	8.0212883e-05
2,973	Functional Dependencies for Graphs	2016	SIGMOD	7.9083516e-05
3,709	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB	7.1780227e-05
5,608	Big Graphs: Challenges and Opportunities	2022	VLDB	6.1514145e-05
6,403	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	5.8859374e-05
7,083	Certus: An Effective Entity Resolution Approach with Graph Differential Dependencies (GDDs)	2019	VLDB	5.7075402e-05
7,330	Discovering Association Rules from Big Graphs	2022	VLDB	5.6435171e-05
8,113	Capturing Associations in Graphs	2020	VLDB	5.484341e-05
8,225	Deducing Certain Fixes to Graphs	2019	VLDB	5.4624971e-05
8,419	Ontology-based Entity Matching in Attributed Graphs	2019	VLDB	5.4282511e-05
9,627	Making It Tractable to Catch Duplicates and Conflicts in Graphs	2023	SIGMOD	5.2434488e-05
10,538	Structural Normalization of Property Graphs	2026	VLDB	5.093636e-05
10,763	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	5.093636e-05
11,659	GRIP: Constraint-based Explanation of Missing Answers for Graph Queries	2021	SIGMOD	5.093636e-05
11,910	Catching Numeric Inconsistencies in Graphs	2018	SIGMOD	5.093636e-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
20	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00056944564
228	Reference Reconciliation in Complex Information Spaces	2005	SIGMOD	0.00023941271
372	HaLoop: Efficient Iterative Data Processing on Large Clusters	2010	VLDB	0.0001981521
442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018398144
485	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017717377
626	Entity Resolution: Theory, Practice & Open Challenges	2012	VLDB	0.00015656958
1,539	Distributed SociaLite: A Datalog-Based Language for Large-Scale Graph Analysis	2013	VLDB	0.000104329
2,055	Dedoop: Efficient Deduplication with Hadoop	2012	VLDB	9.2512023e-05
2,351	From Data Fusion to Knowledge Fusion	2014	VLDB	8.7099618e-05
3,235	Large-Scale Collective Entity Matching	2011	VLDB	7.6139368e-05
3,358	An efficient reconciliation algorithm for social networks	2014	VLDB	7.4900538e-05
5,302	Active Knowledge: Dynamically Enriching RDF Knowledge Bases by Web Services	2010	SIGMOD	6.2745499e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,503	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,564	gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs	2026	VLDB
5	10,558	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB
6	2,190	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD
7	11,756	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD
8	1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB
9	442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
10	8,419	Ontology-based Entity Matching in Attributed Graphs	2019	VLDB