Graph indexing for spatial data traversal in road map databases

This paper proposes a graph indexing technique for processing constrained spatial queries and discusses the application of such a technique to road map databases where the graph topology is relatively stationary. The fundamental idea of our technique is to augment the original graph with selected augmented links so that query processing cost, especially I/O cost, is minimized. Based on the computational results derived from the probabilistic analysis, we found that the proposed graph indexing technique is a promising approach for significantly reducing costs of spatial queries. Scope and purpose Spatial data is found in geographic information systems where data attributes are associated with nodes and links in directed graphs. Queries on spatial data are generally expensive because of the recursive nature of spatial data traversal. We propose a graph indexing technique to expedite queries on spatial data. The graph index is an instrument for early identification of the relevant nodes and links to the query so that repeated accesses to the same data pages can be eliminated. This paper presents the graph indexing technique in the context of road map databases and shows that the graph indexing technique can improve significantly on the efficiency of constrained queries on spatial data. (C) 2000 Elsevier Science Ltd. All rights reserved.