bkd-tree

    1.2.1 • Public • Published

    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 coordinates
    • opts.type.value - array of type strings for the data payload
    • opts.branchFactor - branch factor. default: 4
    • opts.levels - number of levels in the smallest tree. default: 5
    • opts.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 array
    • row.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

    Keywords

    none

    Install

    npm i bkd-tree

    DownloadsWeekly Downloads

    194

    Version

    1.2.1

    License

    BSD

    Unpacked Size

    59.9 kB

    Total Files

    21

    Last publish

    Collaborators

    • andrew_chou
    • substack
    • karissa
    • digidem-admin
    • gmaclennan
    • noffle