Hierarchical Optimization of Optimal Path Finding for Transportation Applications.

Ning Jing, Yun-Wu Huang, Elke A. Rundensteiner: Hierarchical Optimization of Optimal Path Finding for Transportation Applications. CIKM 1996: 261-268

@inproceedings{DBLP:conf/cikm/JingHR96,
  author    = {Ning Jing and
               Yun-Wu Huang and
               Elke A. Rundensteiner},
  title     = {Hierarchical Optimization of Optimal Path Finding for Transportation
               Applications},
  booktitle = {CIKM '96, Proceedings of the Fifth International Conference on
               Information and Knowledge Management, November 12 - 16, 1996,
               Rockville, Maryland, USA},
  publisher = {ACM},
  year      = {1996},
  pages     = {261-268},
  ee        = {db/conf/cikm/JingHR96.html, http://doi.acm.org/10.1145/238355.238550},
  crossref  = {DBLP:conf/cikm/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Efficient path finding is a key requirement for advanced database applications including GIS (Geographic Information Systems) and ITS (Intelligent Transportation Systems). We study the problem in the context of automobile navigation systems where a large number of path requests can be submitted over the transportation network within a short period of time. To guarantee efficient response for path queries, we employ a path view materialization strategy for precomputing the best paths. We tackle the following three issues: (1) memory-resident solutions quickly exceed current computer storage capacity for networks of thousands of nodes, (2) disk-based solutions have been found inefficient to meet the stringent performance requirements, and (3) path views become too costly to update for large graphs. We propose the HEPV (Hierarchical Encoded Path View) approach that addresses these problems while guarantees the optimality of retrieved paths. The experiments reveal that HEPV is more efficient than previously known path finding approaches.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 4, CIKM, DOLAP, GIS, SIGFIDET, ..." and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An2-4 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

CIKM '96, Proceedings of the Fifth International Conference on Information and Knowledge Management, November 12 - 16, 1996, Rockville, Maryland, USA. ACM 1996
Contents

Online Edition

Citation Page

Referenced by

Ning Jing, Yun-Wu Huang, Elke A. Rundensteiner: Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation. IEEE Trans. Knowl. Data Eng. 10(3): 409-432(1998)
Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Integrated Query Processing Strategies for Spatial Path Queries. ICDE 1997: 477-486

Last update Thu May 24 04:14:44 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page