Skip to content
forked from Anish-aak/r-tree

An R-Tree implementation in C, using STR Bulk Loading

License

Notifications You must be signed in to change notification settings

Srijan01/r-tree

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

25 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

R-Tree using STR Bulk Loading

R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional data. This program implements the sort-tile-recursive (STR) bulk loading technique that reads all rectangles from a file in order to construct an R-tree (in memory) for them. This is an implementation of the paper STR: A Simple and Efficient Algorithm for R-Tree Packing, by Scott T. Leutenegger, J. M. Edgington, and Mario A. López

Running the program

This program accepts a text file (.txt) as an argument. The file should be passed as an additional argument while executing the binary (the file should be in the same folder as the compiled binary).

gcc -o rtree rtree.c -lm    # compiling the binary
./rtree data.txt            # assuming that the file is named data.txt

Visualization

Visualization requires formatted input in the form of a CSV file (4 columns, in the order minx, miny, maxx, maxy). Store the CSV file in the same folder as the python file. This can then be simply run by:

python visualize.py     # Enter the name of the CSV file after this

Results

  • For large.txt (105000 data points):

  • For data.txt (21 data points):

About

An R-Tree implementation in C, using STR Bulk Loading

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C 94.9%
  • Python 5.1%