prefix-hash-tree

An extensible prefix hash tree for indexing over distributed hash tables.

npm install prefix-hash-tree

Usage

const { PrefixHashTree } = require('prefix-hash-tree')

// Construct some options, binding the get/put interface for your hash table
const opts = {
  b: 4,
  bitDomain: 160,
  keyEncoding: 'utf8',
  indexID: 'myIndex',
  transform: (oldState = [], newState) => [...oldState, ...newState],
  getFunc: async (key) => {
    const response = await dht.get(key)
    return { phtNode: response.phtNode, metadata: 'whatever you want' }
  },
  putFunc: async (key, value) => {
    await dht.put(key, value)
  }
}

const pht = new PrefixHashTree(opts)
await pht.init()

// Insert some keywords and document records
await pht.insert(pht.unhashedKeyFrom('car'), ['doc1', 'doc2', 'doc3'])
await pht.insert(pht.unhashedKeyFrom('cardamom'), ['doc4', 'doc5'])
await pht.insert(pht.unhashedKeyFrom('cardamom'), ['doc6'])
await pht.insert(pht.unhashedKeyFrom('card'), ['doc2', 'doc6'])
await pht.insert(pht.unhashedKeyFrom('cargo'), ['doc5'])
await pht.insert(pht.unhashedKeyFrom('carnival'), ['doc1', 'doc7'])
await pht.insert(pht.unhashedKeyFrom('cat'), ['doc8', 'doc5', 'doc7', 'doc9'])

// Prefix query
const query1 = await pht.prefixQuery(pht.prefixFrom('card')) // discover keywords 'cardamom', 'card'
const query2 = await pht.prefixQuery(pht.prefixFrom('car')) // discover keywords 'car', 'cardamom', 'card', 'cargo', 'carnival'
const query3 = await pht.prefixQuery(pht.prefixFrom('cat')) // discover keyword 'cat'

// Keyword search
const search1 = await pht.searchExact(pht.unhashedKeyFrom('cardamom')) // ['doc4', 'doc5', 'doc6']
const search2 = await pht.searchExact(pht.unhashedKeyFrom('cat')) // ['doc8', 'doc5', 'doc7', 'doc9']

API

new PrefixHashTree(opts)

Construct a new prefix hash tree over a hash table interface.

await pht.init()

Idempotently initialize the prefix hash tree topology.

pht.unhashedKeyFrom(string)

Construct an unhashed prefix hash tree key, suitable for preserving lexicographic ordering.

await pht.insert(key, val)

Insert a key and value to the prefix hash tree.

await pht.searchExact(key)

Exact match search. Returns the associated value.

await pht.searchLeaf(key)

Find the leaf node (shard) responsible for a key. Returns { phtNode, metadata }.

pht.prefixFrom(string)

Construct a key prefix for use with a prefix query.

await pht.prefixQuery(prefix)

Prefix query. Returns an array of [key, value] pairs.

License

Apache-2.0