Repository files navigation

Documentation:

SpatialIndexing package provides the tools for efficient in-memory indexing ofspatial data inJulia.

using Pkg; Pkg.add("SpatialIndexing")

from Julia REPL.

R-tree organizes data intohierarchical structure and ensures that:

• minimal bounding rectangles (MBRs) of the nodes (rectangles thatencompass all data elements in the subtree) stay compact,
• MBRs of the nodes from the same R-tree level have minimal overlapwith each other.

The key benefit of R-tree is its ability to rebalance itselfand maintain efficient structure while handling dynamic data (massive insertionsand deletions).

SpatialIndexing providesRTree type that supports:

• different R-tree variants (classicR-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 regionreg
• findfirst(tree, reg, [id]),contained_in(tree, reg) andintersects_with(tree, reg) spatial queries

SimpleSpatialIndex stores all data elements in a vector. So, while insertionof new data takes constant time, the time of spatial searches grows linearlywith the number of elements. This spatial index is intended as a referenceimplementation for benchmarking and not recommended for production usage.

TODO

TODO

examples folder containsspiral.jl andpareto.jl examples of using R-treefor storing spatial data.

Other Julia packages for spatial data:

• LibSpatialIndex.jl(libspatialindex wrapper)
• NearestNeighbors.jl
• RegionTrees.jl
• LSH.jl

• 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