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.