Ellipsoidal quadtrees for indexing of global geographical data

Systems for landscape visualization and geographical data handling require methods for efficient data access. Retrieval of data from large geographical databases, ten to thousands of Gbytes, is usually optimized with spatial indexing mechanisms. The simplest form of spatial indexing is achieved by dividing the database into congruent grid cells. The subsequent subdivision of the grid cells can be based on so-called quadtrees. Quadtrees for two-dimensional division and subdivision are appropriate for cartographical data. A geographical database, with objects stored in geocentric or geodetic (geographical) co-ordinates, requires indexing mechanisms that take into account the shape of the Earth. In this paper, we present a method for indexing of geographical data, named Ellipsoidal Quadtrees (EQT). In contrast to other global indexing methods, EQT is based on the Earth ellipsoid and not a spherical approximation. EQT division and subdivision make it possible to divide the Earth surface into a mesh of quadrangles with equal areas. We will demonstrate that EQT is flexible. It can be used for indexing databases of various sizes, including national and global databases. Tests on real data show that the performance of EQT is good.