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: 10053
Venue: VLDB
Year: 2010
Pagerank: 0.00011913289
Overall Rank: 1,454 | 89.89%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
1,180	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013456907
1,285	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00012833377
1,775	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00010602927
2,117	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.5155578e-05
2,409	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.8776858e-05
2,428	VOGUE: Towards A Visual Interaction-aware Graph Query Processing Framework	2013	CIDR	8.8367608e-05
2,551	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.5572574e-05
3,862	A Partition-Based Approach to Structure Similarity Search	2014	VLDB	6.687769e-05
4,072	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	6.4727847e-05
5,854	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.3006473e-05
6,839	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD	4.9109527e-05
9,057	Behavior Query Discovery in System-Generated Temporal Graphs	2016	VLDB	4.4039656e-05
9,058	Semantic SPARQL Similarity Search Over RDF Knowledge Graphs	2016	VLDB	4.4039656e-05
9,580	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	4.3234342e-05
10,163	Enumerating Graph Pattern Matches with ML Oracles	2026	SIGMOD	4.1945683e-05
11,559	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.1945683e-05
11,565	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD	4.1945683e-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
36	Fast Algorithms for Mining Association Rules	1994	VLDB	0.00076161096
181	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.00036992674
203	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00034889335
350	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026365067
612	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.0001920234

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,958	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.8031038e-05
7,307	SUFF: Accelerating Subgraph Matching with Historical Data	2023	VLDB	4.7674113e-05
506	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021475362
203	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00034889335
11,559	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.1945683e-05
10,696	S3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB	4.1945683e-05
4,072	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	6.4727847e-05
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027081079
6,406	Mining and Indexing Graphs for Supergraph Search	2013	VLDB	5.0765917e-05