A New Point Access Method based on Wavelet Trees

Nieves Brisaboa, Miguel Luaces, Gonzalo Navarro, and Diego Seco

The development of index structures that allow efficient retrieval of spatial objects has been a topic of interest in the last decades. Most of these structures have been designed for secondary memory. However, in the last years the price of memory has decreased drastically, and therefore, nowadays it is feasible to place complete spatial indexes in main memory.

In this paper, we focus in a subcategory of spatial indexes named Point Access Methods. These indexes are designed to solve the problem of indexing points. We present a new index structure designed for main memory that keeps a good trade-off between the space needed to store the index and its search efficiency. Our structure is based on a wavelet tree, which was originally designed to index the characters from a text, but which has been successfully used to build self-indexes in areas like information retrieval or image compression.