Spatial data traversal in road map databases
Jun Zhao, Ahmed S. Zaki · 1994
Spatial data are found in geographic information systems such as digital road map databases where city and road attributes are associated with nodes and links in a directed graph. Queries on spatial data are expensive because of the recursive property of graph traversal. We propose a graph indexing technique to expedite spatial queries where the graph topology remains relatively stationary. Using a probabilistic analysis, this paper shows that the graph indexing technique significantly improves the efficiency of constrained spatial queries.