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.3793473e-05
Overall Rank
4,835 | 67.60%
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
952 Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019 SIGMOD 0.00012878316
1,907 Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching 2021 SIGMOD 9.379165e-05
2,226 TurboFlux: A Fast Continuous Subgraph Matching System for Streaming Graph Data 2018 SIGMOD 8.7971869e-05
3,107 GuP: Fast Subgraph Matching by Guard-based Pruning 2023 SIGMOD 7.6265309e-05
4,099 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.7940875e-05
5,271 Cardinality Estimation of Subgraph Matching: A Filtering-Sampling Approach 2024 VLDB 6.1891764e-05
5,486 Diversified Top-k Subgraph Querying in a Large Graph 2016 SIGMOD 6.097643e-05
5,717 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 6.0067263e-05
6,251 BICE: Exploring Compact Search Space by Using Bipartite Matching and Cell-Wide Verification 2023 VLDB 5.8179719e-05
7,595 A Framework for Privacy Preserving Localized Graph Pattern Query Processing 2023 SIGMOD 5.4727106e-05
9,179 In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework 2024 SIGMOD 5.1992749e-05
9,837 NeuSO: Neural Optimizer for Subgraph Queries 2026 SIGMOD 5.1064323e-05
9,882 Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences 2025 VLDB 5.1043481e-05
10,498 Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching 2026 SIGMOD 4.9605343e-05
10,583 Sublime: Selecting Subgraph Matching Algorithms via Machine Learning 2026 SIGMOD 4.9605343e-05
10,747 R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization 2026 SIGMOD 4.9605343e-05
10,805 CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination 2026 VLDB 4.9605343e-05
12,292 Stylus: A Strongly-Typed Store for Serving Massive RDF Data 2018 VLDB 4.9605343e-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.00026634326
215 Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age 2014 SIGMOD 0.00024554257
288 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022009138
333 FG-Index: Towards Verification-Free Query Processing on Graph Databases 2007 SIGMOD 0.00020712452
356 On Graph Query Optimization in Large Networks 2010 VLDB 0.00020086045
439 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB 0.00018247958
446 Trinity: A Distributed Graph Engine on a Memory Cloud 2013 SIGMOD 0.00018135272
485 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017479773
513 Scalable SPARQL Querying of Large RDF Graphs 2011 VLDB 0.00017023182
558 Hexastore: Sextuple Indexing for Semantic Web Data Management 2008 VLDB 0.00016438585
1,180 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB 0.00011600363
1,205 NUMA-aware algorithms: the case of data shuffling 2013 CIDR 0.00011512846
1,417 A Distributed Graph Engine for Web Scale RDF Data 2013 VLDB 0.00010706533
1,813 gStore: Answering SPARQL Queries via Subgraph Matching 2011 VLDB 9.5705978e-05
2,109 TripleBit: a Fast and Compact System for Large Scale RDF Data 2013 VLDB 9.0224381e-05
2,732 x-RDF-3X: Fast Querying, High Update Rates, and Consistency for RDF Databases 2010 VLDB 8.0665111e-05
2,782 Graph Homomorphism Revisited for Graph Matching 2010 VLDB 8.0054142e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,041 Scalable Join Processing on Very Large RDF Graphs 2009 SIGMOD
2 3,771 Multi-Query Optimization for Subgraph Isomorphism Search 2017 VLDB
3 1,988 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB
4 439 Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism 2008 VLDB
5 883 An Efficient SQL-based RDF Querying Scheme 2005 VLDB
6 1,502 Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs 2015 VLDB
7 9,357 Semantic SPARQL Similarity Search Over RDF Knowledge Graphs 2016 VLDB
8 1,813 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,180 An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases 2013 VLDB