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: 11222
Venue: VLDB
Year: 2015
Pagerank: 7.3791229e-05
Overall Rank: 3,477 | 76.15%
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,237	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011545768
2,035	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	9.2787188e-05
2,190	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	8.9804702e-05
2,940	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	7.9381573e-05
5,118	Efficient Streaming Subgraph Isomorphism with Graph Neural Networks	2021	VLDB	6.3580186e-05
6,393	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	5.8879832e-05
7,301	PICASSO: Exploratory Search of Connected Subgraph Substructures in Graph Databases	2017	VLDB	5.6506327e-05
7,845	Graph Querying Meets HCI: State of the Art and Future Directions	2017	SIGMOD	5.5332653e-05
10,089	VINCENT: Towards Efficient Exploratory Subgraph Search in Graph Databases	2022	VLDB	5.1558402e-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
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
442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018398144
727	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014565738
1,231	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011571594
2,328	Towards Graph Containment Search and Indexing	2007	VLDB	8.745748e-05
3,431	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB	7.4189541e-05
6,520	Mining and Indexing Graphs for Supergraph Search	2013	VLDB	5.8535203e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	326	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD
2	3,431	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB
3	352	On Graph Query Optimization in Large Networks	2010	VLDB
4	322	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD
5	2,328	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,631	Updating Graph Indices with a One-Pass Algorithm	2015	SIGMOD
8	442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
9	177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD
10	727	Graph Indexing: Tree + Delta >= Graph	2007	VLDB