Formed in 2009, the Archive Team (not to be confused with the archive.org Archive-It Team) is a rogue archivist collective dedicated to saving copies of rapidly dying or deleted websites for the sake of history and digital heritage. The group is 100% composed of volunteers and interested parties, and has expanded into a large amount of related projects for saving online and digital history.
hierarchical-bit-vector
A hierarchical bit vector (HBV) C++ addon for Node.js.
An HBV is a data structure for storing sets of integers where the largest possible element is known a priori. For sparse sets, enumerating the elements of an HBV is more performant than that of a standard bit vector.
For a more detailed look at HBVs, see the paper written by Glenn & Binkley.
Build instructions
Install dependencies and build the project with npm run install.
Example usage
const HierarchicalBitVector = require('./index.js');
// create a new HBV representing integers in the range [0 ... (2^30 - 1)]
const set = new HierarchicalBitVector.create();
// add an element to the set
set.insert(561);
// remove an element from the set
set.delete(561);
// add multiple elements to the set
set.inserts([1105, 1729, 2465, 2821]);
// remove multiple elements from the set
set.deletes([2465, 2821]);
// check if an element exists within the set
console.log(set.contains(42)); // -> 0
console.log(set.contains(561)); // -> 0
console.log(set.contains(1105)); // -> 1
// find the minimal element in the set, if it exists
console.log(set.min()); // -> 1105
// given n, find the minimal x > n in the set, if it exists
console.log(set.succ(0)); // -> 1105
console.log(set.succ(1105)); // -> 1729
console.log(set.succ(1729)); // -> -1An ES6 implementation has also been provided so that HBVs may be consumed by modern browsers. The API is nearly identical:
// create a new HBV representing integers in the range [0 ... (2^15 - 1)]
const set = new HierarchicalBitVector(16);
// access the entire data structures internal values
console.log(set.vector);
// etc ...