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: 10054
Venue: VLDB
Year: 2010
Pagerank: 0.00011941836
Overall Rank: 1,444 | 89.97%
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
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
1,125	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00013829006
1,280	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00012838714
1,715	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00010776518
2,118	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.5036922e-05
2,402	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.87387e-05
2,418	VOGUE: Towards A Visual Interaction-aware Graph Query Processing Framework	2013	CIDR	8.8499974e-05
2,557	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.5484449e-05
3,864	A Partition-Based Approach to Structure Similarity Search	2014	VLDB	6.6813849e-05
3,894	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	6.6531173e-05
5,903	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.2757528e-05
6,835	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD	4.9065543e-05
9,056	Behavior Query Discovery in System-Generated Temporal Graphs	2016	VLDB	4.3997447e-05
9,057	Semantic SPARQL Similarity Search Over RDF Knowledge Graphs	2016	VLDB	4.3997447e-05
9,523	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	4.3273374e-05
10,163	Enumerating Graph Pattern Matches with ML Oracles	2026	SIGMOD	4.1905499e-05
11,563	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.1905499e-05
11,569	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD	4.1905499e-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.00076114894
182	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.00036955562
202	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00034881375
351	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026351742
616	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00019068362

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,959	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB	5.7992713e-05
7,304	SUFF: Accelerating Subgraph Matching with Historical Data	2023	VLDB	4.7628386e-05
502	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021528261
202	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00034881375
11,563	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.1905499e-05
3,894	Performance and Scalability of Indexed Subgraph Query Processing Methods	2015	VLDB	6.6531173e-05
10,704	S3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB	4.1905499e-05
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027077424
6,386	Mining and Indexing Graphs for Supergraph Search	2013	VLDB	5.0820608e-05