Journal of KIISE:Databases (한국정보과학회논문지:데이타베이스)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

An Approximate Shortest Path Re-Computation Method for Digital Road Map Databases in Mobile Computing Environments

모바일 컴퓨팅 환경에서의 디지털 로드맵 데이타베이스를 위한 근접 최단 경로 재계산 방법

  • Published : 2003.06.01
Download PDF
⟨ Previous Next ⟩

Abstract

One of commercial applications of mobile computing is ATIS(Advanced Traveler Information Systems) in ITS(Intelligent Transport Systems). In ATIS, a primary mobile computing task is to compute the shortest path from the current location to the destination. In this paper, we have studied the shortest path re-computation problem that arises in the DRGS(Dynamic Route Guidance System) in ATIS where the cost of topological digital road map is frequently updated as traffic condition changes dynamically. Previously suggested methods either re-compute the shortest path from scratch or re-compute the shortest path just between the two end nodes of the edge where the cost change occurs. However, these methods we trivial in that they do not intelligently utilize the previously computed shortest path information. In this paper, we propose an efficient approximate shortest path re-computation method based on the dynamic window scheme. The proposed method re-computes an approximate shortest path very quickly by utilizing the previously computed shortest path information. We first show the theoretical analysis of our methods and then present an in-depth experimental performance analysis by implementing it on grid graphs as well as a real digital road map.

모바일 컴퓨팅의 상업적인 응용분야로서, 지능형 교통정보시스템(ITS: Intelligent Transport Systems)의 한 분야인 첨단 여행자 정보시스템(ATIS: Advanced Traveler Information Systems )이 있다. ATIS에서 가장 중요한 모바일 컴퓨팅 태스크는 현재 위치에서 목적지까지의 최단 경로를 계산하는 일이다. 본 논문에서는 ATIS의 동적 경로 안내 시스템(DRGS: Dynamic Route Guidance System)에서 발생하는 최단 경로 재 계산 문제에 대해서 연구하였다. 이 문제는 동적인 교통상태에 따라 디지털 로드 맵 상의 간선 비용이 빈번하게 갱신되기 때문에 발생한다. 기존의 방법들은 처음부터 최단 경로를 재 계산하거나, 또는 단지 비용의 변화가 일어난 간선 상에 있는 양 꼰 노드 사이에 대해서만 최단 경로를 재 계산할 뿐이다. 이러한 방법은 앞서 계산된 최단 경로에 대한 정보를 이용하지 않는다는 점에서 모두 비효율적이다. 이에, 본 논문에서는 효율적인 동적 윈도우 기반의 근접 최단 경로 재 계산 방법(A Dynamic Window-Based Approximate Shortest Path Re-Computation Method)을 제안한다. 이 방법은 앞서 계산된 최단 경로의 정보를 이용하여 최적의 최단 경로에 상당히 근접한 경로를 매우 빠른 시간 안에 계산해 낸다. 우리는 제안한 방법을 이론적으로 분석한 다음 이를 격자 그래프 및 실제 디지털 로드맵 상에 구현하여 철저한 실험적인 성능 분석을 하였다.

Keywords

References

  1. R. Agrawal and H. Iagadish, 'Algorithms for Searching Massive Graphs', In IEEE Transactions on Knowledge and Data Engineering, Vol. 6, No.2, pp. 225-238, April 1994 https://doi.org/10.1109/69.277767
  2. R. Kung, E. Hanson, Y. Ioannnidis, T. Sellis, L. Shapiro, and M. Stonebraker, 'Heuristic Search in Data Base System', In Proc. 1st Int. Workshop Expert Database Systems, pp. 96-107, Oct. 1984
  3. Y. Huang, N. Jing, and E. Rundensteiner, 'Hierarchical Path Views: A Model Based on Fragmentation and Transportation Road Types', In Proc. of the 3rd ACM Workshop on Geographic Information Systems, pp, 93-100, 1995
  4. K. Ishikawa, M. Ogawa, S. Azume, and T. Ito, 'Map Navigation Software of the Electro Multivision of the '91 Toyota Soarer', In Int. Conf. on Vehicle Navigation and Information Systems(VNIS IVHS), IEEE, (991) pp. 463-473
  5. B. Liu, S. Choo, S. Lok, S. Leong, S. Lee, F. Poon, and H. Tan, 'Integrating Case-Based Reasoning, Knowledge-Based Approach and Dijkstra Algorithm for Route Finding', Proc. Tenth Conf. Artificial Intelligence for Applications (CAIA '94), pp, 149-155, 1994 https://doi.org/10.1109/CAIA.1994.323680
  6. J. Shapiro, J. Waxman, and D. Nir, 'Level Graphs and Approximate Shortest Path Algorithms', In Networks, Vol. 22, pp. 691-717, 1992 https://doi.org/10.1002/net.3230220707
  7. T. Yang, S. Shekhar, B. Hamidzadeh, and P. Hancock, 'Path Planning and Evaluation in IVHS Databases', IEEE Int'l Conf. on Vehicle Navigation and Information Systems(VNIS IVHS), pp. 283-290, 1991
  8. R. Goldman, N. Shivakumar, S. Venkstasubramanian, and H. Gracia-Molina, Search in Databases', In Proceedings VLDB Conference, pp. 26-37, 1998
  9. N. Jing, Y. Huang, and E. Rundensteiner, 'Hierarchical Optimization of Optimal Path Finding for Transportation Applications', In Proc. of 5th Int'l Conf. on Information and Knowledge Management, pp. 261-268, 1996 https://doi.org/10.1145/238355.238550
  10. N. Jing, Y. Huang, and E. Rundensteiner, 'Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation', In IEEE Transactions on Knowledge and Data Engineering, Vol. 10, No.3, pp. 409-432, May/June 1998 https://doi.org/10.1109/69.687976
  11. S. Jung and S. Pramanik, 'HiTi Graph Model of Topographical Road Maps in Navigation Systems', Proceedings of the 12th IEEE International Conference on Data Engineering, pp. 76-84, New Orleans, Louisiana, Feb. 1996 https://doi.org/10.1109/ICDE.1996.492091
  12. T. Mohr and C. Pasche, 'A Parallel Shortest Path Algorithm', In Computing, Vol. 40, pp, 281-292, 1988 https://doi.org/10.1007/BF02276912
  13. S. Shekhar, A. Kohli, and M. Coyle, 'Path Computation Algorithms for advanced Traveler Information System (ATIS)', In Proc. IEEE 9th Int'l Conf. Data engineering, pp. 31-39, 1993 https://doi.org/10.1109/ICDE.1993.344080