Query optimization for navigation in geographic information systems.

In the information age, navigation applications such as vehicle route guidance, network routing, and traveler information systems are facing new demands from users for better and faster path services. This dissertation presents novel solutions to today's navigation problems by addressing path computation issues, such as (1) providing stringent response time, (2) capturing dynamically changing measurements (e.g., traffic conditions), (3) scaling up to large maps, and (4) customizing path computation based on ad-hoc user constraints. For navigation such as centralized vehicle route guidance systems, we propose the Hierarchical Encoded Path Views (HEPV) solution to efficiently compute path queries for a large number of users. The HEPV fragments a large map into sub-graphs, organizes them into a hierarchy, and pre-computes all-pair shortest paths for the sub-graphs. HEPV can efficiently compute paths because partial path segments are pre-computed. It also minimizes the path pre-computation and storage costs because sub-graphs are much smaller than the original map. As a result, HEPV can frequently update the pre-computed paths in capturing the dynamic traffic conditions. HEPV is the first hierarchical path per-computation approach that can achieve 100% path accuracy by guaranteeing path optimality. For traveler information services, we present three different types of optimization. First, we develop and experimentally evaluate a graph clustering technique that groups graph links into disk pages based on their spatial proximity. Our experimental results show that this technique significantly improves path computation I/O over alternative clustering solutions. Next, we identify a new navigation query class, called spatial path queries (such as avoiding flood areas), and develop an array of integration strategies for spatial path query processing. We also conduct extensive experiments for establishing guidelines for selecting the best spatial path query processing strategies under given circumstances. Lastly, we proposed several techniques to improve the state-of-the-art methods in spatial query processing. The first of these techniques is a new Breadth-First R-tree Join method which employs global optimization techniques to significantly reduce the I/O cost (up to 50%) in the filter step processing of spatial joins. The second is a solution for the refinement step processing of spatial joins, called Symbolic Intersect Detection, which dramatically reduces the computation cost by more than 50% over the state-of-the-art technology.Ph.D.Applied SciencesComputer scienceUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/130736/2/9811101.pd