项目作者: furstenheim

项目描述 :
Blazingly fast, GC friendly R-Tree
高级语言: Go
项目地址: git://github.com/furstenheim/SimpleRTree.git
创建时间: 2018-03-05T10:47:20Z
项目社区:https://github.com/furstenheim/SimpleRTree

开源协议:

下载


Simple RTree

Simple RTree is a blazingly fast and GC friendly RTree. It handles 1 Million points in 1.2 microseconds for nearest point search
(measured in an i7 with 16Gb of RAM). It is GC friendly, queries require 0 allocations.
Building the index requires exactly 8 allocations and approximately 40 bytes per coordinate.
That is, an index for 1 million points requires approximately 40Mb in the heap.

To achieve this speed, the index has three restrictions. It is static, once built it cannot be changed.
It only accepts points coordinates, no bboxes, lines or ids. And it only accepts (for now) one query, closest point to a given coordinate.

Beware, to achieve top performance one of the hot functions has been rewritten in assembly.
Library works in x86 but it probably won’t work in other architectures. PRs are welcome to fix this deficiency.

Simple Recursive Layout

Installation

  1. go get github.com/furstenheim/SimpleRTree

Basic Usage

The format of the points is a single array where each two coordinates represent a point

  1. import "SimpleRTree"
  2. points := []float64{0.0, 0.0, 1.0, 1.0} // array of two points 0, 0 and 1, 1
  3. fp := SimpleRTree.FlatPoints(points)
  4. r := SimpleRTree.New().Load(fp)
  5. closestX, closestY, distanceSquared := r.FindNearestPoint(1.0, 3.0)
  6. // 1.0, 1.0, 4.0

Documentation

To access the whole documentation you can access the following link.

Benchmark. CPU

These are the benchmarks for finding the nearest point once the index has been built.

  1. BenchmarkSimpleRTree_FindNearestPoint/10-4 10000000 124 ns/op
  2. BenchmarkSimpleRTree_FindNearestPoint/1000-4 3000000 465 ns/op
  3. BenchmarkSimpleRTree_FindNearestPoint/10000-4 2000000 670 ns/op
  4. BenchmarkSimpleRTree_FindNearestPoint/100000-4 2000000 871 ns/op
  5. BenchmarkSimpleRTree_FindNearestPoint/200000-4 2000000 961 ns/op
  6. BenchmarkSimpleRTree_FindNearestPoint/1000000-4 1000000 1210 ns/op
  7. BenchmarkSimpleRTree_FindNearestPoint/10000000-4 1000000 1593 ns/op

Comparison with other libraries

It is hard to find good comparison of RTrees. Best available can be found at Sizmek which gathers benchmarks for RTrees in Java and Scala.
According to that benchmark query times for 10M points vary from 2.7 microseconds to over 100 microseconds, so SimpleRTree performs fairly better.
Performance is even comparable with Boost
for trees using R*-tree algorithm the performance is of 0.12s for 100k searches (i.e. 1.2 microseconds per search), same as SimpleRTree.

We have added SimpleRTree to the following chart of Java libraries (source Sizmek).

comparison-with-other-libraries