DBScholar

Back to papers

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.3954734e-05
Overall Rank
4,819 | 67.62%
DOI
10.14778/2809974.2809981
PDF
Download (CC BY-NC-ND 3.0)

Incoming Non-self Citations Over Time

Authors

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
961 Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019 SIGMOD 0.00012830477
1,901 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 9.4014537e-05
2,212 TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data 2018 SIGMOD 8.8195478e-05
3,165 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.5735255e-05
4,077 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.8156109e-05
5,426 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 6.1332147e-05
5,481 Diversified Top-k Subgraph Querying in a Large Graph 2016 SIGMOD 6.1126446e-05
5,904 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 5.9511271e-05
6,506 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.758981e-05
7,579 A Framework for Privacy Preserving Localized Graph Pattern Query Processing 2023 SIGMOD 5.4908669e-05
9,157 In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework 2024 SIGMOD 5.216524e-05
9,804 NeuSO: Neural Optimizer for Subgraph Queries 2026 SIGMOD 5.1233734e-05
10,264 Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences 2025 VLDB 5.0480912e-05
10,432 Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching 2026 SIGMOD 4.9769913e-05
10,517 Sublime: Selecting Subgraph Matching Algorithms via Machine Learning 2026 SIGMOD 4.9769913e-05
10,686 R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization 2026 SIGMOD 4.9769913e-05
10,744 CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination 2026 VLDB 4.9769913e-05
12,249 Stylus: A Strongly-Typed Store for Serving Massive RDF Data 2018 VLDB 4.9769913e-05
Previous Page 1 / 1 Next

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.00026688651
215 Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age 2014 SIGMOD 0.00024589307
289 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00021960834
332 FG-Index: Towards Verification-Free Query Processing on Graph Databases 2007 SIGMOD 0.00020756016
355 On Graph Query Optimization in Large Networks 2010 VLDB 0.00020116134
438 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018278591
445 Trinity: A Distributed Graph Engine on a Memory Cloud 2013 SIGMOD 0.00018168823
489 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017440023
512 Scalable SPARQL Querying of Large RDF Graphs 2011 VLDB 0.00017053842
557 Hexastore: Sextuple Indexing for Semantic Web Data Management 2008 VLDB 0.00016489266
1,181 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB 0.00011621825
1,206 NUMA-aware algorithms: the case of data shuffling 2013 CIDR 0.00011536099
1,410 A Distributed Graph Engine for Web Scale RDF Data 2013 VLDB 0.00010737126
1,804 gStore: Answering SPARQL Queries via Subgraph Matching 2011 VLDB 9.5980088e-05
2,098 TripleBit: a Fast and Compact System for Large Scale RDF Data 2013 VLDB 9.0487308e-05
2,722 x-RDF-3X: Fast Querying, High Update Rates, and Consistency for RDF Databases 2010 VLDB 8.0926355e-05
2,774 Graph Homomorphism Revisited for Graph Matching 2010 VLDB 8.0313907e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,029 Scalable Join Processing on Very Large RDF Graphs 2009 SIGMOD
2 3,769 Multi-Query Optimization for Subgraph Isomorphism Search 2017 VLDB
3 2,017 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,507 Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs 2015 VLDB
7 9,332 Semantic SPARQL Similarity Search Over RDF Knowledge Graphs 2016 VLDB
8 1,804 gStore: Answering SPARQL Queries via Subgraph Matching 2011 VLDB
9 489 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