Project Overview

Project Members

Sponsors

Publications

Project Overview

In this project, we are developing state-of-the-art map database technology to address the data management needs of ITS applications. Current GIS systems are designed for static maps, typically assuming no or only very infrequent changes. In ITS, we must address the problem of frequent and often real-time changes to the map model in terms of traffic volume, incidents, etc. Current relational DBMS products are designed for SQL type applications, whereas path queries (route computation) as required for ITS are extremely inefficient. Our goal is to address these problems by developing object-oriented map data technology customized to ITS applications.

Our efforts have focused on efficient path computation necessary for route guidance, one of the key requirements for ITS. While other ITS database systems typically use search algorithms (e.g., heuristic A*) to provide for compute-on-demand path finding, we have developed a semi-materialized path view approach that precomputes optimal paths. Advantages of our approach are (1) route computation is very efficient and no longer dependent on the number of route requests per time period, and (2) the storage overhead is minimal compared to a full enumeration of all possible paths. Our algorithms incrementally update the semi-materialized path view structure in response to weight changes on the traffic links of the underlying (possibly cyclic) network. We have extended the semi-materialized path view approach to hierarchical route guidance. This hierarchical extension results in a significant reduction in view storage costs as well as update performance, without any noticeable penalty in terms of path retrieval speed. Our experimental results measuring storage requirements, route retrieval and path view update times, and route accuracy demonstrate the potential of our approach.

In continuation of this project, we are exploring the implementation of our map and route management approach on commercial DBMS platforms, conduct experimental studies of persistent implementations versus main-memory alternatives, and utilize object-oriented spatio-temporal models in order to incorporate expected traffic behavior into path planning.

Project Members

Advisor

Elke Rundensteiner

Graduate Students

Yun-Wu Huang

Ning Jing

Sponsors

Dept. of Transportation, ITS Center of Excellence

Publications

Jing, N., Huang, Y.W., and Rundensteiner, E. A., ``Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation'', accepted for IEEE Transaction on Data and Knowledge Engineering, 1997.

Yun-Wu Huang, Ning Jing and Elke A. Rundensteiner, "Spatial Joins Using R-trees Based on Breadth-First Traversal," 23nd Intl. Conf. on Very Large Data Bases, Athens, Greece, Aug. 1997.

Huang, Y.W., Jing N. and Rundensteiner, E. A., A Cost Model for Estimating the Performance of Spatial Joins Using R-trees, 9th International Conference on Scientific and Statistical Database Management (SSDBM'97), Olympia, Washington, August 11 - 13, 1997.

Huang, Y.W., Jones, M. and Rundensteiner, E. A., ``Improving Spatial Join Processing Using Symbolic Intersect Detection,'' 5th International Symposium on Large Spatial Databases (SSD'97), Berlin, Germany, July 15-18, 1997.

Huang, Y.W., Jing N. and Rundensteiner, E. A., ``Integrated Query Processing Strategies for Spatial Path Queries,'' IEEE Int. Conf. on Data Engineering, (ICDE-13), Birmingham, UK, April 1997. also with a talk.

Jing, N., Huang, Y.W., and Rundensteiner, E. A., ``Hierarchical Optimization of Optimal Path Finding for Transportation Applications'' ACM 5th Int. Conf on Information and Knowledge Management (CIKM'96), Nov. 1996.

Huang, Y.W., Jing, N., and Rundensteiner, E. A., ``Effective Graph Clustering for Path Queries in Digital Map Databases'', ACM 5th Int. Conf on Information and Knowledge Management (CIKM'96), Nov. 1996.

Yun-Wu Huang, Ning Jing and Elke A. Rundensteiner, ``Path Queries for Transportation Networks: Dynamic Reordering and Sliding Window Paging Techniques,'' in Proc. of the 4th ACM Workshop on Geographic Information Systems (ACM-GIS'96), Washington DC, November 1996.

Huang, Y.W., Jing, N., and Rundensteiner, E. A., "Evaluation of Hierarchical Path Finding Techniques for ITS Route Guidance," ITS America, 1996.

Jing, N., Huang, Y.W., and Rundensteiner, E. A., "Hierarchical Optimization of Optimal Path Finding for Transportation Applications," ACM 5th Int. Conf on Information and Knowledge Management (CIKM'95), Nov. 1996.

Huang, Y.W., Jing, N., and Rundensteiner, E. A., "Effective Graph Clustering for Path Queries in Digital Map Databases," ACM 5th Int. Conf on Information and Knowledge Management (CIKM'95), Nov. 1996.

Huang, Y.W., Jing, J., and Rundensteiner, E. A., "Path Queries for Transportation Networks: Dynamic Reordering and Sliding Window Paging Techniques," ACM Workshop on Geographic Information Systems, Nov. 1996.

Huang, Y.W., Jing, N., and Rundensteiner, E. A., ITS RCE Center, Technical Report, 1995.

Huang, Y.W., Jing, N., and Rundensteiner, E. A., ITS RCE Center, Technical Report, June 1995.

Huang, Y.W., Jing, J., and Rundensteiner, E. A., ACM Workshop on Geographic Information Systems, Nov. 1995.

Huang, Y.W., Jing, J., and Rundensteiner, E. A., "A Semi-Materialized View Approach for Route Guidance in Intelligent Vehicle Highway Systems," ACM Workshop on Geographic Information Systems, Nov. 1994.