19 June 2001

A SPATIAL INDEXING FRAMEWORK USING A QUADTREE ORGANIZATION FOR GEOGRAPHIC DATA STORAGE
AND RETRIEVAL

R. Wilson    M. Chung    K. Shaw
Naval Research Laboratory
Stennis Space Center, MS 39529-5004
M. Cobb
University of Southern Mississippi
Hattiesburg, MS

Abstract

The Digital Mapping, Charting and Geodesy Analysis Program of the Naval Research Laboratory has developed an object-oriented digital mapping database prototype, called the Geospatial Information Database (GIDB). This database application is capable of importing any of the National Imagery and Mapping Agency's (NIMA's) Vector Product Format data and converting the data into an object format. Other supported NIMA data types include Raster Product Format, Text Product Standard, and Digital Terraln Elevation Data. The GIDB supports multimedia data as well, including audio, video, and imagery (GW and JPEG).

Our approach involves partitioning the globe into latitude-longitude cells, since retrieval of objects in the application is always based on a user-defined area of interest. Because any spatially referenced data can be indexed by the quadtree, spatial range queries, i.e., which objects are located within a particular area, are efficiently processed for the multiple data types stored in the GIDB. Each object is defined to have a minimum bounding rectangle, or latitude-longitude bounding box, which is used to determine its placement within a quadtree. ln this paper, a brief description of the vector, raster, text, and gridded data types that are stored in the GIDB is presented, followed by a detailed description of the basic quadtree design. The utilization of the resulting quadtree organization is then outlined and discussed; specifically, the method by which objects are placed in the quadtree, as well as the algorithms for object retrieval, are analyzed.

Sponsored by the Marine Corps Warfighting Lab, the Defense Modeling and Simulation Office, and the National Imagery and Mapping Agency s Terrain Modeling Program Office.

Published in proceedings of the First Southern Symposium on Computing (SSC 98), Hattiesburg, MS, December 4-5, 1998.
Naval Research Laboratory Contribution Number NRL/PP/7441 98-0017.
Conference Proceedings