Spatial Index Library

This package was developed by Marios Hadjieleftheriou

Download Source: Download

Description

This package provides a general framework for developing spatial indices. Currently it defines generic interfaces, provides simple main memory and disk based storage managers and a robust implementation of an R*-tree, an MVR-tree and a TPR-tree. For more information please read the README file. In addition the library includes a 3-dimensional R-tree visualization plug-in (example image below; requires Java3D runtime). This library is free software published under the GNU Lesser General Public License. You may copy, modify and use freely.

Supported Features

  • Generic main memory and disk based storage managers.
  • R*-tree index (also supports linear and quadratic splitting).
  • MVR-tree index (a.k.a. PPR-tree).
  • TPR-tree index.
  • Advanced query capabilities, using Strategy and Visitor patterns.
  • Arbitrary shaped range queries, by defining generic geometry interfaces.
  • Large parameterization capabilities, including dimensionality, fill factor, node capacity, etc.
  • STR packing / bulk loading.

References

  1. Antonin Guttman: 'R-trees: A Dynamic Index Structure for Spatial Searching', Proceedings of the ACM SIGMOD, 1984
  2. Nick Roussopoulos, Stephen Kelley, Frederic Vincent: 'Nearest Neighbor Queries', Proceedings of the ACM SIGMOD, 1995
  3. King Lum Cheung, Ada Wai-chee Fu: 'Enhanced nearest neighbor search on the R-tree', SIGMOD Record, vol. 27, num. 3, 1998
  4. Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: 'The R*-tree: An Efficient and Robust Access Method for Points and Rectangles', Proceedings of the ACM SIGMOD, 1990
  5. Thomas Seidl, Hans-Peter Kriegel: 'Optimal Multi-Step k-Nearest Neighbor Search', Proceedings of the ACM SIGMOD, 1998
  6. M. Hadjieleftheriou, E. Hoel, V. J. Tsotras: SaIL: 'A Spatial Index Library for Efficient Application Integration', Geoinformatica, Vol. 9, No. 4, 2005.

Download Source: Download