SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs

Summary: Introduces SAPPER for approximate subgraph indexing and matching in large, noisy graphs. Novelty: hybrid neighborhood units, pre-generated random spanning trees, and a tailored enumeration order enable efficient, scalable approximate search. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10244
Venue: VLDB
Year: 2010
Pagerank: 0.00011571594
Overall Rank: 1,231 | 91.56%
DOI: 10.14778/1920841.1920988

Incoming Non-self Citations Over Time

Authors

1. Shijie Zhang (Case Western Reserve University)
2. Jiong Yang (Case Western Reserve University)
3. Wei Jin (Case Western Reserve University)

BibTeX Citation

@article{zhang_vldb10,
        title = {{SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs}},
        author = {Zhang, Shijie and Yang, Jiong and Jin, Wei},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        doi = {10.14778/1920841.1920988},
        url = {https://doi.org/10.14778/1920841.1920988},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018398144
659	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00015214062
1,102	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012166591
1,394	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.0001093153
1,812	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.6948178e-05
2,285	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.8052998e-05
2,650	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.2920414e-05
3,477	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	7.3791229e-05
3,522	A Partition-Based Approach to Structure Similarity Search	2014	VLDB	7.3491042e-05
4,749	VOGUE: Towards A Visual Interaction-aware Graph Query Processing Framework	2013	CIDR	6.5250721e-05
5,370	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.2436385e-05
7,152	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD	5.6872619e-05
9,149	Semantic SPARQL Similarity Search Over RDF Knowledge Graphs	2016	VLDB	5.3134506e-05
9,207	Behavior Query Discovery in System-Generated Temporal Graphs	2016	VLDB	5.3058708e-05
9,665	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.2406724e-05
10,452	Enumerating Graph Pattern Matches with ML Oracles	2026	SIGMOD	5.093636e-05
11,756	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	5.093636e-05
11,762	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
27	Fast Algorithms for Mining Association Rules	1994	VLDB	0.00052255472
161	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.00027981772
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
326	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00021152829
431	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018577017

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,631	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD
2	6,924	SUFF: Accelerating Subgraph Matching with Historical Data	2023	VLDB
3	352	On Graph Query Optimization in Large Networks	2010	VLDB
4	177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
5	11,756	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD
6	9,383	S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB
7	3,477	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB
8	442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
9	322	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD
10	6,520	Mining and Indexing Graphs for Supergraph Search	2013	VLDB