Space-Efficient Structures for Range Querying
In this web we provide several space-efficient representations of rectangle datasets that can be used in the development of geographic indexes supporting orthogonal range queries.
Source Code
- Space-Efficient Point Query Structure: SE-PQ.
- Wavelet Tree on Rectangles: WTR.
- Interval Stabbing Structures: IS.
- STR R-tree and CR-tree (require Spatial Library): R-tree.
- Common utilities (coordinates encoding, management of input files, etc.): util.
Third-Party Libraries
- Compact Data Structures Library: libcds.
- Marios Hadjieleftheriou's Spatial Library: libspatialindex.
Datasets
- Synthetic Zipf distribution: zipf.tar.gz.
- Synthetic Gauss distribution: gauss.tar.gz.
- Diputación da Coruña. EIEL: webEIEL.
- U.S. Census Bureau. TIGER Products: tiger.
Publications
Preliminary partial versions of this work appeared in Proc. SeCoGIS 2010 (pdf), pp. 32-42, LNCS 6413, and Proc. FUN 2010 (pdf), pp. 77-88, LNCS 6099.
A more detailed description of this project has been published in Information Systems 38(5) (pdf), pp. 635-655, 2013.
About us
We are three researchers from the University of A Coruña (Spain) and one from the University of Chile (Chile).
- Nieves R. Brisaboa (phD). Database Lab. UDC
- Miguel R. Luaces (phD). Database Lab. UDC
- Gonzalo Navarro (phD). Computer Science Department. UChile
- Diego Seco (phD). Database Lab. UDC
Acknowledgements
This work was supported in part by Ministerio de Ciencia e Innovación (PGE and FEDER) [grant TIN2009-14560-C03-02], Xunta de Galicia (FEDER) [grants 10SIN028E and 2010/17], and Fondecyt [1-110066].