본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

정보과학회논문지. Journal of KIISE. 데이타베이스 v.30 no.3, 2003년, pp.296 - 309   피인용횟수: 1

모바일 컴퓨팅 환경에서의 디지털 로드맵 데이타베이스를 위한 근접 최단 경로 재계산 방법
An Approximate Shortest Path Re-Computation Method for Digital Road Map Databases in Mobile Computing Environments

김재훈   (LG전자CC0145603  ); 정성원   (서강대학교 컴퓨터학과UU0000674  ); 박성용   (서강대학교 컴퓨터학과UU0000674  );
  • 초록

    모바일 컴퓨팅의 상업적인 응용분야로서, 지능형 교통정보시스템(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)을 제안한다. 이 방법은 앞서 계산된 최단 경로의 정보를 이용하여 최적의 최단 경로에 상당히 근접한 경로를 매우 빠른 시간 안에 계산해 낸다. 우리는 제안한 방법을 이론적으로 분석한 다음 이를 격자 그래프 및 실제 디지털 로드맵 상에 구현하여 철저한 실험적인 성능 분석을 하였다.


    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.


  • 주제어

    모바일 컴퓨팅 .   디지털 로드맵 .   근접최단경로 .   지능형교통정보시스템 .   격자 그래프.  

  • 참고문헌 (13)

    1. 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 
    2. J. Shapiro, J. Waxman, and D. Nir, 'Level Graphs and Approximate Shortest Path Algorithms', In Networks, Vol. 22, pp. 691-717, 1992 
    3. 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 
    4. R. Goldman, N. Shivakumar, S. Venkstasubramanian, and H. Gracia-Molina, Search in Databases', In Proceedings VLDB Conference, pp. 26-37, 1998 
    5. 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 
    6. 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 
    7. 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 
    8. T. Mohr and C. Pasche, 'A Parallel Shortest Path Algorithm', In Computing, Vol. 40, pp, 281-292, 1988 
    9. 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 
    10. 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 
    11. 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 
    12. 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 
    13. 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 
  • 이 논문을 인용한 문헌 (1)

    1. Bae, Sang-Woo ; Kim, Seung-Hyun ; Lee, Jong-Hyun ; Koo, Ho-Bon ; Lee, Yun-Rae 2010. "Slope Navigation based on the Cut Slope Data Management System" 한국지형공간정보학회지 = Journal of the korean society for geospatial information science, 18(4): 71~77     

 저자의 다른 논문

  • 정성원 (19)

    1. 2001 "다중 에이전트 시스템 구축을 위한 아키텍쳐 개발방법 및 지능형 교통 시스템에의 응용" 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용 28 (7): 478~492    
    2. 2001 "디지털 로드맵 데이터베이스에서 효율적인 동적 경로 질의어 처리 방안" 정보과학회논문지. Journal of KIISE. 데이타베이스 28 (3): 430~448    
    3. 2003 "이동컴퓨팅 환경에서 데이타의 접근빈도 및 시맨틱 관계를 고려한 방송 방법" 정보과학회논문지. Journal of KIISE. 데이타베이스 30 (5): 476~493    
    4. 2003 "무선 환경에서의 이동 클라이언트를 위한 효율적인 캐시 일관성 유지 방안" 정보과학회논문지. Journal of KIISE. 데이타베이스 30 (6): 606~628    
    5. 2004 "멀티무선채널을 갖는 모바일 환경에서 브로드캐스트 데이타를 위한 인덱스 할당 방법" 정보과학회논문지. Journal of KIISE. 정보통신 31 (1): 37~52    
    6. 2004 "모바일 컴퓨팅 환경에서 협업추천 모형을 이용한 캐시 적재 기법" 퍼지 및 지능시스템학회 논문지 = Journal of fuzzy logic and intelligent systems 14 (6): 687~692    
    7. 2006 "무선 브로드캐스트 환경에서 편향된 엑세스 패턴을 가진 모바일 트랜잭션을 위한 효과적인 동시성 제어 기법" 정보과학회논문지. Journal of KIISE. 데이타베이스 33 (1): 69~85    
    8. 2006 "다중 방송채널을 위한 데이타 할당" 정보과학회논문지. Journal of KIISE. 데이타베이스 33 (1): 86~101    
    9. 2007 "모바일 환경에서 타임스탬프 트리 기반 캐시 무효화 보고 기법" 정보과학회논문지. Journal of KIISE. 데이타베이스 34 (3): 217~231    
    10. 2008 "단일 무선 채널에서 브로드캐스트 디스크 프로그램을 위한 지수 인덱스 기법" 정보과학회논문지. Journal of KIISE. 데이타베이스 35 (6): 518~532    
  • 박성용 (22)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기