static-range-query

Fast n-dimensional orthogonal range searches for static point sets

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 4D points 
var D = 4, 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

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

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 You can terminate the search early by returning true from cb, for example:

rangeQuery([0, 0, 0], [100, 100, 100], function(i) {
 
  if(=== 100) {
    console.log("found it!")
    return true
  }
 
  //Continue processing .... 
  return false
})

Credits

(c) 2013 Mikola Lysenko. MIT License