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



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).


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].