Source code of R-trees and variations

Here you will find source codes for the original R-tree and some of its most popular variants (R+-tree, R*-tree, ...), mainly used for indexing data in in low-dimensional space, R-tree extensions for high-dimensional spaces (TV-tree, X-tree, ...), and R-tree-based indexing techniques for temporal and spatio-temporal data (Segment R-tree, TB-tree, ...). Last but not least, a number of other useful links, including links to GiST, XXL etc. libraries for programming purposes.

R-trees and variants (in low-dimensional space)

R-tree [Gut84]:

• C implementation by Timos Sellis @NTUA: Rtree.tar.gz (187k)

• C++ and Java implementations by Marios Hadjieleftheriou @UCR: link to source code and visual  interface
  supports main memory and disk based storage managers, advanced query capabilities, arbitrary shaped range queries etc. 

• Perl implementation by Ari Jolma @TKK: link to source code 
  

R⁺ -tree [SRF87]:

• C implementation by Timos Sellis @NTUA: Rplus.tar.gz (90k)

• Java implementation by Dimitris Papadias @HKUST: Rplus-java.zip (18k)
  with visual interface (requires Symantec Visual Cafe)
  

R*-tree [BKSS90]:

• C++ and Java implementations by Marios Hadjieleftheriou @UCR: link to source code and visual  interface
  supports main memory and disk based storage managers, advanced query capabilities, arbitrary shaped range queries etc. 

• C implementation by Bernhard Seeger @Marburg: RStarTree.tar.gz (50k) original link

• C++ implementation by Hans-Peter Kriegel et al. @Munich: Rstar_Berchtold.tar.gz (30k)

• Java implementation by Dimitris Papadias @HKUST: Rstar-java.zip (59k)
  with a nice interface involving several types of spatial queries
  

cR-tree [BPT02]:

• C++ implementation in GiST platform by Sotiris Brakatsoulas @CTI: myamdb.tar.gz  (3M) mylibgist.tar.gz (8M) hmetis.tar.gz (300k) readme.txt  

R-tree extensions for high-dimensional spaces

TV-tree [LJF94]:

• C implementation by King-Ip (David) Lin @UMD TV.tar.gz (310k)

X-tree [BKK96]:

• C++ implementation by Hans-Peter Kriegel @Munich: xtree.tar.gz (30k)

R-tree-based indexing techniques for temporal and spatio-temporal data

Segment R-tree [KS89]:

• Java implementation by Vassilis Tsotras @UCR: SR-tree-java.zip (24k)
  note: does not support overflow pages

 MV3R-tree [TP01] for historical timestamp and interval queries:

• C++ implementation by Yufei Tao @HKUST: mv3r.zip (260k)

TPR*-tree [TPS03] for predictive queries:

• C++ implementation by Yufei Tao @HKUST: tpr_star.zip (980k)

FNR-tree [Fre03] for objects moving on (and constrained by) fixed networks:

• VB implementation by Elias Frentzos @NTUA: zip files README file