Multi-Query Optimization for Subgraph Isomorphism Search

Summary: Multi-query optimization for subgraph isomorphism that jointly exploits overlapping subgraphs across queries, via a data structure to detect and organize them. A heuristic plan maximizes reuse of cached intermediates with a balanced caching scheme and adaptation of single-query solvers to reuse cached results; experiments show gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11594
Venue: VLDB
Year: 2017
Pagerank: 7.1780227e-05
Overall Rank: 3,709 | 74.56%
DOI: 10.14778/3021924.3021929

Incoming Non-self Citations Over Time

Authors

1. Xuguang Ren (Griffith University)
2. Junhu Wang (Griffith University)

BibTeX Citation

@article{ren_vldb17,
        title = {{Multi-Query Optimization for Subgraph Isomorphism Search}},
        author = {Ren, Xuguang and Wang, Junhu},
        journal = {PVLDB},
        series = {{VLDB} '17},
        volume = {10},
        number = {3},
        pages = {121--132},
        doi = {10.14778/3021924.3021929},
        url = {https://doi.org/10.14778/3021924.3021929},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,006	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012699518
5,118	Efficient Streaming Subgraph Isomorphism with Graph Neural Networks	2021	VLDB	6.3580186e-05
7,365	Extending Graph Patterns with Conditions	2020	SIGMOD	5.6329929e-05
9,432	MITra: A Framework for Multi-Instance Graph Traversal	2023	VLDB	5.2701501e-05
9,693	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	5.2351259e-05
10,050	Towards the Scheduling of Vertex-constrained Multi Subgraph Matching Query	2020	SIGMOD	5.1685424e-05
10,084	MAVIS: Materialized View for Subgraph Matching	2026	SIGMOD	5.1573064e-05
10,204	Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching	2026	SIGMOD	5.093636e-05
10,606	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	5.093636e-05
10,763	Rule-Based Graph Cleaning with GPUs on a Single Machine	2025	SIGMOD	5.093636e-05
11,074	Mayura: Exploiting Similarities in Motifs for Temporal Co-Mining	2025	VLDB	5.093636e-05
11,208	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
153	Common Expression Analysis in Database Applications	1982	SIGMOD	0.00029032276
294	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022253507
352	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020375193
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
485	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017717377
659	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00015214062
1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.0001179597
1,487	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010615297
2,973	Functional Dependencies for Graphs	2016	SIGMOD	7.9083516e-05
3,251	Keys for Graphs	2015	VLDB	7.5963955e-05
4,417	Massively Multi-Query Join Processing in Publish/Subscribe Systems	2007	SIGMOD	6.7148702e-05
4,832	Association Rules with Graph Patterns	2015	VLDB	6.4877e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,204	Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching	2026	SIGMOD
2	10,419	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD
3	442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
4	659	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD
5	10,050	Towards the Scheduling of Vertex-constrained Multi Subgraph Matching Query	2020	SIGMOD
6	1,487	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB
7	1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB
8	2,190	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD
9	5,370	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
10	5,118	Efficient Streaming Subgraph Isomorphism with Graph Neural Networks	2021	VLDB