Taming Subgraph Isomorphism for RDF Query Processing

Summary: Bridges RDF homomorphism evaluation and general subgraph-isomorphism search by removing injectivity from a state-of-the-art algorithm. TurboHOM++ combines query transformation and optimizations, outperforming RDF engines by up to five orders of magnitude in-memory. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h7868596e6379f060
Venue: VLDB
Year: 2015
Pagerank: 6.3985024e-05
Overall Rank: 4,817 | 67.62%
DOI: 10.14778/2809974.2809981

Incoming Non-self Citations Over Time

Authors

1. Jinha Kim (Oracle)
2. Hyungyu Shin (Pohang University of Science and Technology)
3. Wook-Shin Han (Pohang University of Science and Technology)
4. Sungpack Hong (Oracle)
5. Hassan Chafi (Oracle)

BibTeX Citation

@article{kim_vldb15,
        title = {{Taming Subgraph Isomorphism for RDF Query Processing}},
        author = {Kim, Jinha and Shin, Hyungyu and Han, Wook-Shin and Hong, Sungpack and Chafi, Hassan},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {11},
        pages = {1238--1249},
        doi = {10.14778/2809974.2809981},
        url = {https://doi.org/10.14778/2809974.2809981},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
960	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012836554
1,900	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	9.4059063e-05
2,211	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	8.8237249e-05
3,164	GuP: Fast Subgraph Matching by Guard-based Pruning	2023	SIGMOD	7.5771124e-05
4,075	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	6.8188389e-05
5,422	Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach	2024	VLDB	6.1361195e-05
5,477	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.1155396e-05
5,901	Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation	2021	SIGMOD	5.9539374e-05
6,504	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	5.7617085e-05
7,573	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD	5.4934674e-05
9,148	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	5.2189946e-05
9,797	NeuSO: Neural Optimizer for Subgraph Queries	2026	SIGMOD	5.1257999e-05
10,258	Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences	2025	VLDB	5.050482e-05
10,420	Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching	2026	SIGMOD	4.9793485e-05
10,506	Sublime: Selecting Subgraph Matching Algorithms via Machine Learning	2026	SIGMOD	4.9793485e-05
10,675	R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization	2026	SIGMOD	4.9793485e-05
10,734	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	4.9793485e-05
12,243	Stylus: A Strongly-Typed Store for Serving Massive RDF Data	2018	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 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
215	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00024598661
288	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021969641
332	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020765078
355	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020124083
438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018286607
444	Trinity: A Distributed Graph Engine on a Memory Cloud	2013	SIGMOD	0.00018177351
490	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017438618
511	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017061883
557	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00016497067
1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011627329
1,206	NUMA-aware algorithms: the case of data shuffling	2013	CIDR	0.00011541214
1,410	A Distributed Graph Engine for Web Scale RDF Data	2013	VLDB	0.00010742208
1,804	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB	9.6025094e-05
2,097	TripleBit: a Fast and Compact System for Large Scale RDF Data	2013	VLDB	9.053015e-05
2,721	x-RDF-3X: Fast Querying, High Update Rates, and Consistency for RDF Databases	2010	VLDB	8.0964644e-05
2,773	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.0351713e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,026	Scalable Join Processing on Very Large RDF Graphs	2009	SIGMOD
2	3,767	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB
3	2,014	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB
4	438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB
5	882	An Efficient SQL-based RDF Querying Scheme	2005	VLDB
6	1,506	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB
7	9,323	Semantic SPARQL Similarity Search Over RDF Knowledge Graphs	2016	VLDB
8	1,804	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB
9	490	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD
10	1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB