ibf

Invertible Bloom Filter as described by Eppstein et al. in What's the Difference? Efficient Set Reconciliation without Prior Context.

Implemented with typed arrays. No external dependencies. standard style.

The example in this README is run as the package's test suite.

Configuration

Initialization

var IBF = require('ibf')
var assert = require('assert')
var xxh = require('xxhashjs').h32

var cellCount = 100

var seeds = [0x0000, 0xAAAA, 0xFFFF]

var options = {
  cellCount: cellCount,

  checkHash: function (idBuffer) {
    var digest = xxh(idBuffer, 0x1234)
    var digestBuffer = new ArrayBuffer(4)
    new Uint32Array(digestBuffer)[0] = digest
    return digestBuffer
  },

  keyHashes: seeds.map(function (seed) {
    return function (id) {
      return xxh(id, seed) % cellCount
    }
  }),

  // Keys will be SHA-2 digests of 8 * 32 = 256 bits.
  idSumOctets: 32,

  // Internal hashes will be 32-bit murmur digests.
  hashSumOctets: 4
}

var filter = new IBF(options)

assert.deepStrictEqual(filter.arrayBuffer.byteLength, 4000)

assert.throws(function () {
  IBF({})
})

Inserting, Removing, and Querying

var crypto = require('crypto')

var keys = {}
;['a', 'b', 'c', 'd'].forEach(function (example) {
  keys[example] = crypto.createHash('sha256')
    .update('this is ' + example)
    .digest()
    .buffer // Keys are ArrayBuffers.
})

filter.insert(keys.a)
assert(filter.has(keys.a), 'has A')
assert(filter.additional(keys.a), 'A is additional')
assert(!filter.missing(keys.a), 'A is not missing')

assert(!filter.has(keys.b), 'does not have B')
assert(!filter.additional(keys.b), 'B is not additional')
assert(!filter.missing(keys.b), 'B is not missing')

filter.insert(keys.c)
assert(filter.has(keys.c), 'has C')

filter.remove(keys.c)
assert(!filter.has(keys.c), 'no longer has C')

Cloning

var clone = filter.clone()

clone.remove(keys.d)

assert(clone.has(keys.a), 'clone has A')
assert(clone.missing(keys.d), 'clone missing D')

Subtraction and Decoding

var hasABC = IBF(options)
hasABC.insert(keys.a)
hasABC.insert(keys.b)
hasABC.insert(keys.c)

var hasCD = IBF(options)
hasCD.insert(keys.c)
hasCD.insert(keys.d)

var difference = hasABC.clone()
difference.subtract(hasCD)

var decoded = difference.decode()

assert(decoded !== false)

assert.deepStrictEqual(decoded.additional.length, 2)

function toHex (x) { return Buffer.from(x).toString('hex') }

assert(decoded.additional.some(function (element) {
  return toHex(element) === toHex(keys.a)
}), 'additional A')

assert(decoded.additional.some(function (element) {
  return toHex(element) === toHex(keys.b)
}), 'additional B')

assert.deepStrictEqual(decoded.missing.length, 1)

assert(decoded.missing.some(function (element) {
  return toHex(element) === toHex(keys.d)
}), 'missing D')