Orthogonal range searches in polylog time
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
Example
RangeTree/Classes
.gitignore
.swift-version
.travis.yml
LICENSE
README.md
RangeTree.podspec
_Pods.xcodeproj

README.md

RangeTree

CI Status Version License Platform

A range tree allows you to perform orthorgonal range searches in polylogarithmic time. i.e. If you had a bunch of points in two-dimensional space, and you want to quickly figure out what points have an x coordinate between a and b, and a y coordinate between c and d, this is the module for you.

This module implements an n-dimensional range tree. You define how many dimensions you need by implementing the RangeTreePoint protocol. Note that you will see a performance penalty versus a naive Array.filter if your dataset is too small. See the section on performance to gauge if your dataset is large enough to benefit from this data structure.

Usage

  1. Implement the RangeTreePoint protocol (it's already implemented on Int, Double, and CGPoint for you as part of this module)

    public protocol RangeTreePoint {
        associatedtype Position: Comparable
        static var dimensions: Int { get}
        func positionIn(dimension: Int) -> Position
    }
    
    // Sample implementation
    extension CGPoint: RangeTreePoint {
        public typealias Position = CGFloat
        public static var dimensions = 2
        public func positionIn(dimension: Int) -> Position {
            return dimension == 0 ? self.x : self.y
        }
    }
  2. Construct a RangeTree

    let a = RangeTree<Double>(values: [8, 1, 10, 4, 2, 7, 5, 3, 9, 6])
  3. Query for a range

    a.valuesInRange(rangePerDimension: (3.0, 6.0)) // => [3.0, 4.0, 5.0, 6.0]
  4. Modify the RangeTree

    a.insert(4.5)
    a.valuesInRange(rangePerDimension: (3.0, 6.0)) // => [3.0, 4.0, 4.5, 5.0, 6.0]

Performance

Quad-core 2.8 GHz i7 Retina MacBook Pro:

  • Constructing a tree
    • 1000 points: 0.133s
    • 10000 points: 1.104s
    • 100000 points: 8.420s
    • 1000000 points: 55.377s
  • Querying a tree
    • 1000 points: 0.001s (naive Array.filter: 0.000s) -- slower
    • 10000 points: 0.002s (naive Array.filter: 0.004s) -- 2x faster
    • 100000 points: 0.008s (naive Array.filter: 0.029s) - 3.6x faster
    • 1000000 points: 0.056s (naive Array.filter: 0.266s) - 4.8x faster

1.3 GHz Core m7 12" MacBook:

  • Constructing a tree
    • 1000 points: 0.206s
    • 10000 points: 1.323s
    • 100000 points: 10.413s
    • 1000000 points: 85.719s
  • Querying a tree
    • 1000 points: 0.002s (naive Array.filter: 0.001s) -- slower
    • 10000 points: 0.004s (naive Array.filter: 0.007s) -- 1.8x faster
    • 100000 points: 0.013s (naive Array.filter: 0.038s) -- 2.9x faster
    • 1000000 points: 0.089s (naive Array.filter: 0.436s) -- 4.9x faster

Example & Tests

To run the example project, clone the repo, and run pod install from the Example directory first.

Installation

RangeTree is available through CocoaPods. To install it, simply add the following line to your Podfile:

pod "RangeTree"

Author

Ben Ng, me@benng.me

License

RangeTree is available under the MIT license. See the LICENSE file for more info.