Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets
Summary: Introduces reachability queries over disk-resident spatiotemporal contact datasets. ReachGrid constructs only query-relevant contact subgraphs, while ReachGraph uses multiscale precomputed reachability; disk-aware layouts yield 76% average gains over prior methods. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Houtan Shirani-Mehr (University of Southern California)
- 2. Farnoush Banaei-Kashani (University of Southern California)
- 3. Cyrus Shahabi (University of Southern California)
BibTeX Citation
@article{shiranimehr_vldb12,
title = {{Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets}},
author = {Shirani-Mehr, Houtan and Banaei-Kashani, Farnoush and Shahabi, Cyrus},
journal = {PVLDB},
series = {{VLDB} '12},
volume = {5},
number = {9},
pages = {848--859},
doi = {10.14778/2311906.2311912},
url = {https://doi.org/10.14778/2311906.2311912},
year = {2012}
}Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,278 | Simple, Fast, and Scalable Reachability Oracle | 2013 | VLDB | 7.5712342e-05 |
| 12,211 | Folk-IS: Opportunistic Data Services in Least Developed Countries | 2014 | VLDB | 5.093636e-05 |
| 13,451 | Estimating Spread of Contact-Based Contagions in a Population Through Sub-Sampling | 2021 | VLDB | - |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 433 | Scalable Network Distance Browsing in Spatial Databases | 2008 | SIGMOD | 0.00018532516 |
| 679 | GRAIL: Scalable Reachability Index for Large Graphs | 2010 | VLDB | 0.00015055389 |
| 2,853 | Indexing Large Trajectory Data Sets With SETI* | 2003 | CIDR | 8.0383547e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,603 | Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond | 2020 | VLDB |
| 2 | 2,575 | K-Reach: Who is in Your Small World | 2012 | VLDB |
| 3 | 7,322 | DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs | 2022 | VLDB |
| 4 | 3,979 | Reachability Querying: An Independent Permutation Labeling Approach | 2014 | VLDB |
| 5 | 5,044 | Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs | 2021 | VLDB |
| 6 | 9,132 | HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs | 2023 | SIGMOD |
| 7 | 9,625 | I/O Efficient Label-Constrained Reachability Queries in Large Graphs | 2024 | VLDB |
| 8 | 11,850 | Top-k Queries over Digital Traces | 2019 | SIGMOD |
| 9 | 746 | Efficiently Answering Reachability Queries on Very Large Directed Graphs | 2008 | SIGMOD |
| 10 | 1,796 | Reachability Queries on Large Dynamic Graphs: A Total Order Approach | 2014 | SIGMOD |