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: 11190
Venue: VLDB
Year: 2015
Pagerank: 6.5251089e-05
Overall Rank: 4,748 | 67.43%
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
1,006	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012699518
2,182	TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data	2018	SIGMOD	9.010121e-05
2,190	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD	8.9804702e-05
3,194	GuP: Fast Subgraph Matching by Guard-based Pruning	2023	SIGMOD	7.6491858e-05
4,983	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	6.4127092e-05
5,370	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.2436385e-05
5,942	Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach	2024	VLDB	6.0334209e-05
6,325	Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation	2021	SIGMOD	5.9125893e-05
6,393	BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification	2023	VLDB	5.8879832e-05
8,586	A Framework for Privacy Preserving Localized Graph Pattern Query Processing	2023	SIGMOD	5.4073203e-05
9,440	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	5.2680376e-05
9,617	NeuSO: Neural Optimizer for Subgraph Queries	2026	SIGMOD	5.2434488e-05
10,204	Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching	2026	SIGMOD	5.093636e-05
10,294	Sublime: Selecting Subgraph Matching Algorithms via Machine Learning	2026	SIGMOD	5.093636e-05
10,488	R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization	2026	SIGMOD	5.093636e-05
10,552	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	5.093636e-05
10,952	Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences	2025	VLDB	5.093636e-05
11,944	Stylus: A Strongly-Typed Store for Serving Massive RDF Data	2018	VLDB	5.093636e-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
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
241	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00023654664
294	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022253507
326	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00021152829
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
436	Trinity: A Distributed Graph Engine on a Memory Cloud	2013	SIGMOD	0.00018504439
485	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017717377
500	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017413839
542	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00016838296
1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.0001179597
1,203	NUMA-aware algorithms: the case of data shuffling	2013	CIDR	0.00011671169
1,387	A Distributed Graph Engine for Web Scale RDF Data	2013	VLDB	0.00010949523
1,774	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB	9.7870727e-05
2,053	TripleBit: a Fast and Compact System for Large Scale RDF Data	2013	VLDB	9.2518674e-05
2,669	x-RDF-3X: Fast Querying, High Update Rates, and Consistency for RDF Databases	2010	VLDB	8.2742823e-05
2,718	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.209788e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,979	Scalable Join Processing on Very Large RDF Graphs	2009	SIGMOD
2	3,709	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB
3	2,035	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB
4	431	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB
5	859	An Efficient SQL-based RDF Querying Scheme	2005	VLDB
6	1,487	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB
7	9,149	Semantic SPARQL Similarity Search Over RDF Knowledge Graphs	2016	VLDB
8	1,774	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB
9	485	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