期刊
PROCEEDINGS OF THE VLDB ENDOWMENT
卷 15, 期 11, 页码 3199-3212出版社
ASSOC COMPUTING MACHINERY
DOI: 10.14778/3551793.3551863
关键词
-
资金
- Australian Research Council [DP200103650, LP180100018]
- Hong Kong Research Grants Council [16202722]
- Hong Kong Jockey Club Charities Trust
- Australian Research Council [LP180100018, DP200103650] Funding Source: Australian Research Council
Route planning has a significant impact on our daily lives, but existing algorithms often generate similar paths and lead to congestion. Therefore, we propose a solution to diversify the top-k paths between OD pairs, ensuring their similarities are below a threshold while minimizing the total length.
Route planning is ubiquitous and has a profound impact on our daily life. However, the existing path algorithms tend to produce similar paths between similar OD (Origin-Destination) pairs because they optimize query results without considering their influence on the whole network, which further introduces congestions. Therefore, we investigate the problem of diversifying the top-k paths between an OD pair such that their similarities are under a threshold while their total length is minimal. However, the current solutions all depend on the expensive graph traversal which is too slow to apply in practice. Therefore, we first propose an edge deviation and concatenation-based method to avoid the expensive graph search in path enumeration. After that, we dive into the path relations and propose a path similarity computation method with constant complexity, and propose a pruning technique to improve efficiency. Finally, we provide the completeness and efficiency-oriented solutions to further accelerate the query answering. Evaluations on the real-life road networks demonstrate the effectiveness and efficiency of our algorithm over the state-of-the-art.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据