Documentation: 
SpatialIndexing package provides the tools for efficient in-memory indexing of
spatial data in Julia.
using Pkg; Pkg.add("SpatialIndexing")from Julia REPL.
R-tree organizes data into hierarchical structure and ensures that:
- minimal bounding rectangles (MBRs) of the nodes (rectangles that encompass all data elements in the subtree) stay compact,
- MBRs of the nodes from the same R-tree level have minimal overlap with each other.
The key benefit of R-tree is its ability to rebalance itself and maintain efficient structure while handling dynamic data (massive insertions and deletions).
SpatialIndexing provides RTree type that supports:
- different R-tree variants (classic R-tree, R*-tree, linear and quadratic node splits)
insert!(tree, item),delete!(tree, item)for element-wise insertion and deletion- bulk-loading of data using Overlap-minimizing Top-down (OMT) approach (
load!(tree, data)) subtract!(tree, reg)for removing data within specified regionregfindfirst(tree, reg, [id]),contained_in(tree, reg)andintersects_with(tree, reg)spatial queries
SimpleSpatialIndex stores all data elements in a vector. So, while insertion
of new data takes constant time, the time of spatial searches grows linearly
with the number of elements. This spatial index is intended as a reference
implementation for benchmarking and not recommended for production usage.
TODO
TODO
examples folder contains spiral.jl and pareto.jl examples of using R-tree
for storing spatial data.
Other Julia packages for spatial data:
- A.Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching” Proc. 1984 ACM-SIGMOD Conference on Management of Data (1985), pp.47-57.
- N. Beckmann, H.P. Kriegel, R. Schneider, B. Seeger, "The R*-tree: an efficient and robust access method for points and rectangles" Proc. 1990 ACM SIGMOD international conference on Management of data (1990), p.322
- T. Lee and S. Lee, "OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree", CAiSE Short Paper Proceedings (2003) paper