Augmenting SAND with a spherical data model

Houman Alborzi and Hanan Samet

Computer Science Department
University of Maryland
College Park, MD

Email: houman@cs.umd.edu, hjs@umiacs.umd.edu


SAND is a spatial database and information browser system developed at University of Maryland which supports 2D and 3D data models. In this abstract we describe our experience in adding a spherical data model to SAND which enables it to perform spatial queries on spherical data and to browse their results in an incremental manner. In particular, we focus on the issues that arise in adding a spherical data model to a database that has been built on the basis of the planar data model. Special emphasis is place on how the data structure were chosen for the task. We also describe the various geometrical primitives that were needed for modeling spherical data as well as the algorithms that were required in our implementation. As SAND is based on the quadtree representation, a natural method for adding spherical data to SAND was to find a spherical adaptation of the quadtree. We mapped the sphere into a quadtree representation by projecting the sphere onto a cube, and then constructed the quadtree on the faces of cube. Alternatively, it is also possible to map the sphere into a plane, and then simply use a planar quadtree. We discuss some of the differences between these approaches. We also describe the display models and visual query mechanisms used in spherical SAND to ease the task of navigating through the data. By adding a spherical sector primitive, we make it possible for users to locate data on the sphere which are around a great circle of the sphere. The same primitive allows users to query the database using a range of view from any point on the sphere.