SYMPOSIUM MINISYMPOSIA

MINISYMPOSIUM ABSTRACT

The Digital Mapping, Charting and Geodesy Analysis Program (DMAP) of the Naval Research Laboratory has developed an object-oriented (OO) 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~Rs (NIMA~Rs) 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 Terrain Elevation Data.  The GIDB supports multimedia data as well, including audio, video, and imagery (GIF and JPEG). 

These supported data types are stored in quadtree data structures within the GIDB.  A quadtree is an indexing structure used for the storage and retrieval of two-dimensional data.  The principle upon which it is based is simply the regular recursive subdivision of blocks of spatial data into four equal-sized cells, or quadrants.  Cells are successively subdivided until some criterion is met, usually either:  (1) each cell contains homogeneous data, e.g., a single "feature" for vector data, or rasters containing the same value (known as a region quadtree), or (2) a preset number of decomposition iterations has been performed.  Thus, the cells of a quadtree are of a standard size (in powers of two) and are non-overlapping in terms of areal representation.  A tree structure is then constructed by arranging each cell as the parent of its component quadrant cells.  This structuring leads to a tree whose nodes at any level of the tree are all of the same size, that size being exactly one-fourth the size of the nodes at the next higher level of the tree.

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 spacially 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.  In 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.

Getting More Information

To obtain more information about the meeting send e-mail to: fscc98@pax.st.usm.edu.

Return to Minisymposia
Return to PAX
Return to USM

USM
inquire@delphi.st.usm.edu
Updated
http://pax.st.usm.edu