static-range-query

Given a collection of points in n-dimensional space, preprocesses these points so that orthogonal range queries can be computed efficiently. Internally, this library is built using range trees.

Example

var preprocess = require("static-range-query")

//Generate 10000 3D points
var D = 3, N = 10000
var points = new Array(N)
for(var i=0; i<N; ++i) {
  var p = new Array(D)
  for(var j=0; j<N; ++j) {
    p[j] = Math.random() * 1000
  }
  points[i] = p
}

//Construct query data structure
var rangeQuery = preprocess(points)

//Now execute a range query!
rangeQuery([2, 5, 0.25, -10], [10, 50, 5, 30], function(i) {
  console.log("In range: ", i , points[i])
})

Install

npm install static-range-query

API

var rangeQuery = require("static-range-query")(points)

Preprocesses the point set so that orthogonal range queries can be evaluated efficiently.

• points is an array of points (each point is represented as a tuple of D numbers)

Returns A rangeSearch() function (see below) which evaluates range queries on the point set.

Time Complexity O(points.length * log(points.length)^points[0].length)

Space Complexity O(points.length * log(points.length)^points[0].length)

Notes Internally, this function builds a range tree and binds it to the query method

rangeQuery(lo, hi, cb(index))

Evaluates a range query on the point set.

• lo is a lower bound on the bounding rectangle to query
• hi is an upper bound on the bounding rectangle to query
• cb is a callback which gets called once per each point in the range with the index of a point.

Time Complexity O(log(points.length)^points[0].length + k) where k is the number of points processed in the range.

Note The points are visited in lexicographic order

Other Note You can terminate the search early by returning true from cb, for example:

rangeQuery([0, 0, 0], [100, 100, 100], function(i) {

  if(i === 100) {
    console.log("found it!")
    return true
  }

  //Continue processing ....
  return false
})

When should I use this library?

Preprocessing the point set is relatively slow, mostly due to the creation of many typed arrays. On the other hand, queries are pretty fast with this library. If you are only going to do a few queries, you are better off using brute force. On the other hand, if you have a big data set and are willing to wait for preprocessing to finish, then this library may be a good choice for you.

Credits

(c) 2013 Mikola Lysenko. MIT License