|
Title |
A Fun Application of Compact Data Structures
to Indexing Geographic Data |
|
Authors |
Nieves Brisaboa, Miguel Luaces, Gonzalo Navarro, Diego Seco |
|
Publication date |
2010 |
|
Abstract |
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 fields 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. |
|
Pages |
77-88 |
|
Conference name |
International Conference on Fun with Algorithms |
|
Publisher |
Springer-Verlag (Berlin/Heidelberg, Germany) |
|
Reference URL |
|
