A Fun Application of Compact Data Structures to Indexing Geographic Data Author(s): Nieves R. Brisaboa, Miguel R. Luaces, Gonzalo Navarro, Diego Seco Keywords: geographic data, MBR, range query, wavelet tree
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.
I must confess that after reading this article more than once, I still puzzle over: “Our experiments, featuring GIS-like scenarios, show that our index is a relevant and funnier alternative to classical spatial indexes, such as the R-tree ….”
I admit to being drawn to esoteric and even odd solutions but I would not describe most of them as being “funnier” than an R-tree.
For all that, the article will be useful to anyone developing topic maps for use with spatial indexes and is a good introduction to wavelet trees.
Questions:
- Create an annotated bibliography of spatial indexes. (date limit, last five (5) years)
- Create an annotated bibliography of spatial data resources. (date limit, last five (5) years)
- How would you use MBRs (Minimum Bounding Rectangles) for merging purposes in a topic map? (3-5 pages, no citations)
[…] A Fun Application of Compact Data Structures to Indexing Geographic Data « Another Word For It […]
Pingback by AVL tree implementation help…? — November 25, 2010 @ 7:38 am