An efficient path computation model for hierarchically structured topographical road maps
Tóm tắt
In this paper, we have developed a HiTi (Hierarchical MulTi) graph model for structuring large topographical road maps to speed up the minimum cost route computation. The HiTi graph model provides a novel approach to abstracting and structuring a topographical road map in a hierarchical fashion. We propose a new shortest path algorithm named SPAH, which utilizes HiTi graph model of a topographical road map for its computation. We give the proof for the optimality of SPAH. Our performance analysis of SPAH on grid graphs showed that it significantly reduces the search space over existing methods. We also present an in-depth experimental analysis of HiTi graph method by comparing it with other similar works on grid graphs. Within the HiTi graph framework, we also propose a parallel shortest path algorithm named ISPAH. Experimental results show that inter query shortest path problem provides more opportunity for scalable parallelism than the intra query shortest path problem.
Từ khóa
#Computational modeling #Roads #Navigation #Computational efficiency #Performance analysis #Shortest path problem #Concurrent computing #Cost function #Automobiles #Space explorationTài liệu tham khảo
shekhar, 1997, Materialization Trade-Offs in Hierarchical Shortest Path Algorithms, Proc 1997 Symp Spatial Databases
rosenthal, 1987, Traversal Recursion: A Practical Approach to Supporting Recursive Applications, Proc IEEE Third Int'l Conf Data Eng, 580
10.1016/0004-3702(74)90026-5
10.1002/net.3230220707
10.1109/ICDE.1993.344080
10.1007/BF02276912
pearl, 1984, Heuristics Intelligent Search Strategies for Computer Problem Solving
10.1109/32.75418
10.1016/S0167-8655(98)00110-X
miller, 1993, Automatic Mesh Partitioning, Sparse Matrix Computations Graph Theory Issues and Algorithms, 10.1007/978-1-4613-8369-7_3
ausiello, 1990, Incremental Algorithms for Minimal Length Paths, Proc First Ann ACM-SIAM Symp Discrete Algorithms, 12
10.1109/69.277767
10.1109/ICDE.1993.344038
10.1145/88636.88888
10.1109/ICDE.1989.47238
10.1287/opre.20.5.993
10.1109/SFCS.1991.185417
10.1137/0209046
liu, 1994, Integrating Case-Based Reasoning, Knowledge-Based Approach and Dijkstra Algorithm for Route Finding, Proc 10th Conf Artificial Intelligence for Applications (CAIA '94), 149
kung, 1984, Heuristic Search in Data Base System, Proc First Int'l Workshop Expert Database Systems, 96
10.1145/67544.66949
10.1109/69.567054
10.1109/69.687976
10.1007/3-540-55966-3_21
10.1145/301250.301380
10.1109/ICDE.1990.113477
10.1145/238355.238550
10.1109/32.9055
charniak, 1985, Introduction to Artificial Intelligence
10.1145/191839.191928
10.1109/ICDE.1993.344027
10.1111/j.1467-8640.1988.tb00287.x
yang, 0
10.1145/99935.99944
ishikawa, 0
10.1145/155271.155273
ioannidis, 1988, Efficient Transitive Closure Algorithms, Proc 14th VLDB Conf, 382
10.1145/238355.238497
huang, 1995, Hierarchical Path Views: A Model Based on Fragmentation and Transportation Road Types, Proc Third ACM Workshop Geographic Information Systems, 93
10.1109/ICDE.1993.344025
houstma, 1993, Data Fragmentation for Parallel Transitive Closure Strategies, Proc IEEE Ninth Int'l Conf Data Eng, 447
goldman, 1998, Proximity Search in Databases, Proc 24th VLDB Conf, 26
10.1016/0004-3702(77)90005-4