DBScholar

Back to papers

Computing Label-Constraint Reachability in Graph Databases

Summary: Tree-based index framework for edge-labeled graphs enabling label-constraint reachability. Uses directed maximal weighted spanning tree and sampling to compress generalized transitive closure; experiments on real and synthetic data show efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h073c65167b640ae4
Venue
SIGMOD
Year
2010
Pagerank
8.3335732e-05
Overall Rank
2,534 | 82.97%
DOI
10.1145/1807167.1807183

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{jin_sigmod10,
        title = {{Computing Label-Constraint Reachability in Graph Databases}},
        author = {Jin, Ruoming and Hong, Hui and Wang, Haixun and Ruan, Ning and Xiang, Yang},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807183},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807183},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank Citing Paper Year Venue Pagerank
2,604 K-Reach: Who is in Your Small World 2012 VLDB 8.2302549e-05
2,734 Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017 SIGMOD 8.0789676e-05
3,523 Efficiently Answering Regular Simple Path Queries on Large Labeled Networks 2019 SIGMOD 7.2343247e-05
4,915 Horton+: A Distributed System for Processing Declarative Reachability Queries over Partitioned Graphs 2013 VLDB 6.356048e-05
5,109 A Trichotomy for Regular Simple Path Queries on Graphs 2013 PODS 6.2695208e-05
5,301 Discovering Your Selling Points: Personalized Social Influential Tags Exploration 2017 SIGMOD 6.189668e-05
6,177 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 5.8598586e-05
6,765 DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs 2022 VLDB 5.6872079e-05
7,377 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 5.5395908e-05
7,724 Minimum Strongly Connected Subgraph Collection in Dynamic Graphs 2024 VLDB 5.4672516e-05
9,805 I/O Efficient Label-Constrained Reachability Queries in Large Graphs 2024 VLDB 5.1257999e-05
11,205 Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025 SIGMOD 4.9793485e-05
11,561 Efficient Regular Simple Path Queries under Transitive Restricted Expressions 2024 VLDB 4.9793485e-05
11,891 Answering Regular Path Queries through Exemplars 2022 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Previous Page 1 / 1 Next

Semantically Similar Papers