Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Simple non-academic performance comparison of available open source implementations of R-tree spatial index using linear, quadratic and R* balancing algorithms as well as bulk loading.
C++ Shell
Branch: master
Failed to load latest commit information.
bin/ci Disable benchmarks run on travis-ci
cmake/modules Fix SPATIALINDEX_INCLUDE_DIR location.
results Add new results and charts
.gitignore Ignore tmp directory
.travis.yml Remove comments
CMakeLists.txt Fix case-sensitive string comparison
LICENSE_1_0.txt Add BSL license file
README.md Add extra libraries plan
benchmark_boost_geometry.cpp Revert incomplete change
benchmark_spatialindex.cpp Test for series fo index capacities
configure.bat Set BGI_ENABLE_CT by default
configure.sh
high_resolution_timer.hpp Add high res timer
results.txt Add more results from Linux/GCC.
run_benchmark.bat Change result logs extension to .dat
run_benchmark.sh Allow to specify run-time folder for results
spatial_index_benchmark.hpp Strip seconds indicator

README.md

spatial_index_benchmark

Simple non-academic performance comparison of available open source implementations of R-tree spatial index using linear, *quadratic and R-star balancing algorithms as well as bulk loading (Sort-Tile-Recurse or combined methods).

List of currently measured libraries:

More libraries have been suggested, see the GitHub Issues.

Build Status

Requirements

  • C++11 compiler
  • CMake
  • Boost headers current SVN trunk which includes required internal utilities:
    • boost/geometry/index/detail/rtree/utilities/statistics.hpp - added in r84649
    • boost/geometry/index/detail/rtree/pack_create.hpp - added in r84720
  • libspatialindex headers and libraries (for Windows, use OSGeo4W.

Results

First prototype, API usage and parameters matched as much as I could, hopefully without major bugs.

TODO: explain details

Complete set of result logs in results directory.

Visual C++ 11.0 (32-bit build)

HW: Intel(R) Xeon(R) CPU E5-2687W 0 @ 3.10GHz, 16 GB RAM; OS: Windows 7 64-bit SW: Visual Studio 2012

  • Loading times for each of the R-tree construction methods

load libspatialindex

load boost::geometry

  • Query times for each of the R-tree construction methods

query libspatialindex

query boost::geometry

Legend


  • bgi - boost::geometry::index (_rt is dynamic variant: L,Q,R etc. parameters specified at run-time)
  • lsi - libspatialindex
  • ct - Boost.Geometry-only, compile-time specification of rtree parameters
  • rt (or non suffix) - Boost.Geometry-only, run-time specification of rtree parameters
  • L - linear
  • Q - quadratic
  • R - rstar
  • itr (or no suffix) - iterative insertion method of building rtree
  • blk - bulk loading method of building R-tree (Split-Tile-Recurse for lsi, custom algorithm for bgi)

  • insert 1000000 - number of objects small random boxes

  • query 100000 - number of instersection-based queries with random boxes 10x larger than those inserted
  • stats generated using lsi's API and purposely written visitor for Boost.Geometry (not yet in Boost trunk)

Disclaimer

This project is driven by curiosity and for my own purposes, with hope to obtain useful and interesting results, for myself and others too. I do not have any objective of making ultimate performance shootout. This is not a rocket science, but a simple set of C++ programs, with likelyhood of bugs or inconsistencies. Found any, please report. Comments and improvements are always welcome!

Authors

  • Mateusz Loskot
  • Adam Wulkiewicz

License

Distributed under the Boost Software License, Version 1.0. See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt.

Something went wrong with that request. Please try again.