Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2310.08213 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916632200216576 |
|---|---|
| author | Zhang, Mengxuan Zhou, Xinjie Li, Lei Liu, Ziyi Trajcevski, Goce Huang, Yan Zhou, Xiaofang |
| author_facet | Zhang, Mengxuan Zhou, Xinjie Li, Lei Liu, Ziyi Trajcevski, Goce Huang, Yan Zhou, Xiaofang |
| contents | Shortest Path (SP) computation is a fundamental operation in many real-life applications such as navigation on road networks, link analysis on social networks, etc. These networks tend to be massive, and graph partitioning is commonly leveraged to scale up the SP algorithms. However, the Partitioned Shortest Path (PSP) index has never been systematically investigated. Moreover, few studies have explored its index maintenance in dynamic networks. In this paper, we survey the dynamic PSP index and propose a universal scheme for its design and analysis. Specifically, we first review the SP algorithms and put forward a novel structure-based partition method classification to facilitate the selection of partition methods. Furthermore, we summarize the existing Pre-boundary PSP strategy and propose two novel strategies (No-boundary and Post-boundary) to improve its index performance. Lastly, we propose a universal scheme with three dimensions (SP algorithm, partition method, and PSP strategy) to facilitate the analysis and design of the PSP index. Based on this scheme, we put forward five new PSP indexes with a prominent query or update efficiency performance. Extensive experiments are conducted to evaluate the performance of the PSP index and the effectiveness of the proposed techniques, with valuable guidance on the PSP index design. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_08213 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Universal Scheme for Dynamic Partitioned Shortest Path Index: Survey, Improvement, and Experiments Zhang, Mengxuan Zhou, Xinjie Li, Lei Liu, Ziyi Trajcevski, Goce Huang, Yan Zhou, Xiaofang Databases Shortest Path (SP) computation is a fundamental operation in many real-life applications such as navigation on road networks, link analysis on social networks, etc. These networks tend to be massive, and graph partitioning is commonly leveraged to scale up the SP algorithms. However, the Partitioned Shortest Path (PSP) index has never been systematically investigated. Moreover, few studies have explored its index maintenance in dynamic networks. In this paper, we survey the dynamic PSP index and propose a universal scheme for its design and analysis. Specifically, we first review the SP algorithms and put forward a novel structure-based partition method classification to facilitate the selection of partition methods. Furthermore, we summarize the existing Pre-boundary PSP strategy and propose two novel strategies (No-boundary and Post-boundary) to improve its index performance. Lastly, we propose a universal scheme with three dimensions (SP algorithm, partition method, and PSP strategy) to facilitate the analysis and design of the PSP index. Based on this scheme, we put forward five new PSP indexes with a prominent query or update efficiency performance. Extensive experiments are conducted to evaluate the performance of the PSP index and the effectiveness of the proposed techniques, with valuable guidance on the PSP index design. |
| title | A Universal Scheme for Dynamic Partitioned Shortest Path Index: Survey, Improvement, and Experiments |
| topic | Databases |
| url | https://arxiv.org/abs/2310.08213 |