Performance and Scalability of Indexed Subgraph Query Processing Methods

Summary: Systematic benchmark of six indexed subgraph-query methods across graph size, density, labels, dataset cardinality, and query size. Real and synthetic experiments expose tradeoffs in index construction/size, query latency, false positives, and scalability. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h28475b53f840a665
Venue: VLDB
Year: 2015
Pagerank: 7.2501249e-05
Overall Rank: 3,506 | 76.43%
DOI: 10.14778/2824032.2824046

Incoming Non-self Citations Over Time

Authors

1. Foteini Katsarou (University of Glasgow)
2. Nikos Ntarmos (University of Glasgow)
3. Peter Triantafillou (University of Glasgow)

BibTeX Citation

@article{katsarou_vldb15,
        title = {{Performance and Scalability of Indexed Subgraph Query Processing Methods}},
        author = {Katsarou, Foteini and Ntarmos, Nikos and Triantafillou, Peter},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {12},
        pages = {1566--1577},
        doi = {10.14778/2824032.2824046},
        url = {https://doi.org/10.14778/2824032.2824046},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,180	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011627669
1,900	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	9.4059063e-05
2,014	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	9.1832045e-05
2,824	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	7.9698957e-05
5,218	Efficient Streaming Subgraph Isomorphism with Graph Neural Networks	2021	VLDB	6.2231041e-05
6,504	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	5.7617085e-05
7,450	PICASSO: Exploratory Search of Connected Subgraph Substructures in Graph Databases	2017	VLDB	5.5238477e-05
7,985	Graph Querying Meets HCI: State of the Art and Future Directions	2017	SIGMOD	5.4126006e-05
10,303	VINCENT: Towards Efficient Exploratory Subgraph Search in Graph Databases	2022	VLDB	5.040157e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026700508
332	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020765078
438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018286607
443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018197688
736	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014363536
1,244	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011353487
2,376	Towards Graph Containment Search and Indexing	2007	VLDB	8.5543073e-05
3,499	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB	7.2549774e-05
6,642	Mining and Indexing Graphs for Supergraph Search	2013	VLDB	5.7238453e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	332	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD
2	3,499	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB
3	355	On Graph Query Optimization in Large Networks	2010	VLDB
4	330	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD
5	2,376	Towards Graph Containment Search and Indexing	2007	VLDB
6	1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB
7	6,760	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD
8	443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
9	176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
10	736	Graph Indexing: Tree + Delta >= Graph	2007	VLDB