首页 | 本学科首页   官方微博 | 高级检索  
     


Optimization and evaluation of shortest path queries
Authors:Edward P. F. Chan  Heechul Lim
Affiliation:(1) School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada
Abstract:We investigate the problem of how to evaluate efficiently a collection of shortest path queries on massive graphs that are too big to fit in the main memory. To evaluate a shortest path query efficiently, we introduce two pruning algorithms. These algorithms differ on the extent of materialization of shortest path cost and on how the search space is pruned. By grouping shortest path queries properly, batch processing improves the performance of shortest path query evaluation. Extensive study is also done on fragment sizes, cache sizes and query types that we show that affect the performance of a disk-based shortest path algorithm. The performance and scalability of proposed techniques are evaluated with large road systems in the Eastern United States. To demonstrate that the proposed disk-based algorithms are viable, we show that their search times are significant better than that of main-memory Dijkstra's algorithm.
Keywords:Shortest path queries  Route queries  Query evaluation and optimization  Graph pruning  Disk-based algorithms  Graph algorithms
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号