A Fun Application of Compact Data Structures
to Indexing Geographic Data
Nieves Brisaboa, Miguel Luaces, Gonzalo Navarro, and Diego Seco
The way memory hierarchy has evolved in recent decades has opened
new challenges
in the development of indexing structures in general and spatial access
methods in particular. In
this paper we propose an original approach to represent geographic data based
on compact data
structures used in other elds such as text or image compression. A wavelet
tree -based structure
allows us to represent minimum bounding rectangles solving geographic range
queries in logarithmic
time. A comparison with classical spatial indexes, such as the R-tree, shows
that our structure can
be considered as a fun, yet seriously competitive, alternative to these
classical approaches.