PTIL: Partitioned Tree-Cover Interval Labeling for Restricted-Domain Reachability Queries

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Research Area

Tags

Resources

Abstract

Reachability queries are a core operation in graph analytics. Existing labeling methods assume a global query space and construct uniform labels for all vertices. In practice, however, many systems issue queries over semantically structured endpoint domains such as V_s x V_t, where only a subset of vertices serve as meaningful sources or targets. This mismatch makes global labeling redundant and inefficient. We propose Partitioned Tree-Cover Interval Labeling (PTIL), a restricted-domain reachability indexing framework that extends classical Tree-Cover Labeling. PTIL timestamps only target vertices and stores compact disjoint intervals at sources, reducing each query to a single membership test while avoiding unnecessary global labels. By partitioning targets into groups, PTIL provides an explicit and predictable space-time trade-off: finer grouping yields lower latency at the cost of larger index size. PTIL also supports dynamic updates to endpoint domains. We further develop two instantiations: PTIL-g, a grouped scheme for scalable domain-aligned indexing, and PTIL-p, which additionally leverages query distributions for further prioritization when available. Experiments on real and synthetic graphs show that PTIL-g achieves order-of-magnitude lower query latency than state-of-the-art baselines, while PTIL-p provides additional gains under skewed workloads, with near-linear and predictable space-time behavior.

Author Affiliations

@article{he2027ptil,
  title = {PTIL: Partitioned Tree-Cover Interval Labeling for Restricted-Domain Reachability Queries},
  author = {He, Huangleshuai and Yang, Zhengyi and Tang, Yifu and Chen, Zebin and Wen, Dong and Luo, Qi and Zhang, Tianming},
  volume = {30},
  number = {1},
  pages = {34--46},
  doi = {10.48786/EDBT.2027.04},
  url = {https://openproceedings.org/2027/conf/edbt/paper_22.pdf},
  keywords = {Database Technology},
  language = {en},
  publisher = {OpenProceedings.org},
  year = {2027},
  isbn = {978-3-89318-106-3},
  issn = {2367-2005}
}