Spatial databases, addressing the growing data management and analysis needs of spatial applications such as geographic information systems, have been an active area of research for more than two decades. This research has produced a taxonomy of models for space, spatial data types and operators, spatial query languages and processing strategies, as well as spatial indexes and clustering techniques. However, more research is needed to improve support for network and field data, as well as query processing (e.g., cost models, bulk load). Another important need is to apply spatial data management accomplishments to newer applications, such as data warehouses and multimedia information systems. The objective of this paper is to identify recent accomplishments and associated research needs of the near term.

The shortest-path problem is an essential component of many applications including Advanced Traveler Information Systems (ATIS), computer networks, etc. A hierarchical routing algorithm decomposes the original graph into a set of fragment graphs and also into a boundary graph which summarizes the fragment graphs. A fully memoized hierarchical routing algorithm pre-computes and stores the shortest-path data structure and the shortest-path-cost data structure for the graph fragments, as well as for the boundary graph. The storage cost of the fully memoized approach can be reduced by a virtual or a hybrid memoization approach, where few or none of the relevant data structures have been pre-computed. This paper achieves two firsts. We use a real graph with 123,000 nodes and 313,000 edges, which is two orders of magnitude larger than the graphs used in related work. Second, the paper analyzes the effect of memoizing individual data structures for the storage overhead and computation time of A/sup */-based hierarchical routing algorithms. Analysis and experiments with the Twin Cities metropolitan road-map show that memoizing the shortest-path-cost data structure for the boundary graph provides the best savings in computation time, for a given amount of storage and a small number of fragments. Memoizing the relevant part of the shortest-path-cost data structure for the fragment graphs provides the next best savings, followed by memoizing the shortest-path data structure for the boundary graph.