International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
supports levels of detail aligned with the levels in geoindex. As
an example; the original application and reason for developing
geoindex is global terrain representation. The main concepts
have been presented in (Kolar 2004).
2.5 Implementation
An implementation of the presented indexing method has been
made using Java in a single class. Distribution of centroids
given a division coefficient has been coded as a method as well
as obtaining proximity cell for a point on a given level. In order
to facilitate the application following methods were added:
method for encoding and decoding centroid coordinates into
unique identifiers; method for computing vertices of the cell;
and method for obtaining neighboring cells.
The implementation has been made using double numeric
precision. (64-bit float number). This limits the division
coefficient to be at most equal to 1073741823. Using this
division coefficient would mark cells on the Earth surface with
extent of approximately two centimeters.
As storage PostgreSQL has been used. PostgreSQL is an open
source object-relational DBMS. For creation and management
of the indexing data structures has been used B+-tree provided
by PostgreSQL. Communication with the database has been
made through JDBC.
The data used where GTOPO30 datasets that is freely available
as global DTM. For sake of providing notion of performance
time measurements from processing 28800000 points (GTOPO
tile) are provided. Measurements were made with the prototype
implementation and PostgeSQL running on 2.5GHz Xeon
machine with IGB RAM.
Processing the points using geoindex and storing them in
PostgreSQL lasts 58 minutes and 28 seconds. Building an index
in PostgreSQL using B+-tree and vacuum analyze take 14
minutes and 52 seconds. Note that in the first measurement also
other processing than using geoindex is included, e.g. parsing
and coordinate transformation. These results are assumed only
for better imagination.
3. CONCLUSION
This article overviewed the main concepts of geographic
indexing---a new spatial indexing technique using global grids.
Global grids provide a uniform approach to "divide and
conquer” manner for management of geographic data.
Geoindex is a generally applicable indexing method that could
be applied globally with a possibility to index with virtually
arbitrary spatial resolution.
The used global grid is based on Voronoi tessellation. This is
based on a simple algorithm for distributing semi-regular cells
around the origin that has been also described. Cells that are
used for indexing are defined algorithmically. Hence, in order
to use geoindex there is no need to instantiate any cells, e.g., to
store any data about them in the memory or on a storage device.
Geoindex can be seen as a spatial extension for indexing
techniques used by ordinary RDBMS. The spatial division and
mapping to the identifiers can be done by geoindex as a
separate process while the actual search tree, e.g., B--tree, is
constructed and maintained inside RDBMS, where our data can
672
be stored. This provides many possibilities for use with existing
systems.
Although recursive division of the global grid is impossible, the
algorithmic definition and distribution of the cells allows
dealing with multiple levels of the grid. Regardless number of
levels geoindex performs search for the proximity cell in
constant time.
Geoindex can be applied to any 3D spatial data or 2D data on
surface of the spheroid. However, it has been designed for
spatial data distributed in 3D around certain central point, e.g.,
spatial data on or near to the surface of celestial bodies, e.g.
planets.
Strong feature of geoindex is complete elimination of
cartographic projection. When using geoindex together with 3D
graphics enabled application there is no need to enforce
presentation in map plane. This provides a significant
simplification of the process between geographic data
acquisition and exploitation/consumption of the data. Also
underlying deviations common for all cartographic projections
can be avoided consequently.
A disadvantage of presented mechanism is its application with
rasters, which would be a complex task. This is due to the
variations in the shape of the division scheme provided by
geoindex. This “unfortunate” characteristic does not allow a
straightforward alignment with strictly given spatial structure of
raster data. This fact leaves geoindex suitable mainly for vector
spatial data. Another disadvantage is that the scheme cannot be
divided recursively, although this is de facto compensated by
introducing the concept of levels.
In future work the focus will be given to definitions for more
queries that can efficiently exploit the indexing approach.
Along with queries the main concern is to elaborate specific
applications of geoindex for various data representations of
geographic features. Of particular interest is representation of
the terrain and representation of linear features e.g. roads or
rivers. Also application to rasters would deserve more
substantial research.
REFERENCES
Aasgaard, R., 2002. Projecting a regular grid onto a sphere or
ellipsoid. In: Advances in Spatial Data Handling, Richardson,
D. and Oosterom, van P., Springer-Verlag, 339-350.
Dutton, G. 1989. Planetary modelling via hierarchical
tesselation. In: Proceedings of Ninth International Symposium
on Automated Cartography (Auto-Carto 9), Bethesda, MD,
USA, pp. 462-471.
Kolar, J. 2004. Representation of geographic terrain surface
using global indexing. In: Proceedings of Twelfth International
Conference on Geoinformatics. Gavle, SWE.
Lukatela, H., 1987. Hipparchus geopositioning model: an
overview. In: Proceedings of Eighth International Symposium
on Automated Cartography (Auto-Carto 8), Baltimore, USA.
Oosterom, van P. and Vijlbrief, T., 1996. The spatial location
code. In: The Seventh International Symposium on Spatial Data
Handling. Delft, the Netherlands.
gc
in
he
al
h:
ge
G
