bkd-tree v1.2.1
bkd-tree
bkd tree implementation using random-access storage
This module implements some of the bkd tree paper and is very fast. However, the memory usage can be high at times and some features of the paper, such as the grid bulk load algorithm, are not yet implemented.
The robustness and atomicity of these data structures has not yet been thoroughly tested.
example
insert 5000 points to in-memory storage then search those points for
-0.5 <= x <= -0.4 and -0.9 <= y <= -0.85
var ram = require('random-access-memory')
function storage (name, cb) { cb(null,ram()) }
var bkd = require('bkd-tree')(storage, {
branchFactor: 4,
type: {
point: [ 'float32be', 'float32be' ],
value: [ 'uint32be' ]
},
compare: function (a, b) { return a.value[0] === b.value[0] }
})
var N = 5000
var batch = []
for (var i = 0; i < N; i++) {
var x = Math.random()*2-1
var y = Math.random()*2-1
batch.push({ type: 'insert', point: [x,y], value: [i+1] })
}
var bbox = [-0.5,-0.9,-0.4,-0.85]
bkd.batch(batch, function (err) {
if (err) console.error(err)
bkd.query(bbox, function (err, values) {
if (err) console.error(err)
else console.log(values)
})
})
output:
[ { point: [ -0.4952811002731323, -0.8651710152626038 ],
value: [ 1404 ] },
{ point: [ -0.46114417910575867, -0.8699662089347839 ],
value: [ 300 ] },
{ point: [ -0.4253665506839752, -0.8783734440803528 ],
value: [ 1869 ] },
{ point: [ -0.41438907384872437, -0.8694494962692261 ],
value: [ 3807 ] } ]
api
var BKD = require('bkd-tree')
var bkd = BKD(storage, opts)
Create a new bkd
instance from a random-access storage
instance and:
opts.type.point
- array of type strings for the coordinatesopts.type.value
- array of type strings for the data payloadopts.branchFactor
- branch factor. default: 4opts.levels
- number of levels in the smallest tree. default: 5opts.compare(a,b)
- boolean comparison function required for deletes
The dimensionality of the coordinates should match the length of the
opts.type.value
length.
The type strings listed in opts.type.point
and opts.type.value
can be:
- float32be, float32le, float64be, float64le
- uint8, uint16be, uint16le, uint32be, uint32le
- int8, int16be, int16le, int32be, int32le
Any of these types can have a [n]
quantity at the end. When n > 1
, the
corresponding value for the type will be a typed array except for uint8 which is
a Buffer
(which is also a Uint8Array).
bkd.batch(rows, cb)
Write or remove documents from an array of rows
. Each row
in the rows
array should have:
row.type
-'delete'
or'insert'
row.point
- coordinate arrayrow.value
- array of value types
var stream = bkd.query(bbox)
bkd.query(bbox, cb)
Search for records inside a bounding box bbox
.
Obtain the results with the returned pull-stream stream
or from
cb(err, results)
to get an array of results.
The bbox
should contain all the minimum values for each dimension followed by
all the maximum values for each dimension. In 2d, the bbox is
[minX,minY,maxX,maxY]
, or the more familiar [west,south,east,north]
.
Values exactly on the border are included in the results.
install
npm install bkd-tree
license
BSD