DistinctSketch

A DistinctSketch is 4,096 one-byte registers. Adding a value hashes it and raises one register; merging two sketches takes each register’s maximum, so sketches built by different workers, time slices or machines combine into the sketch of everything they saw. The estimate is within about 1.6% (one standard error) of the true number of distinct values. Values hash by what they are, not how they are stored: numbers by their bits (-0 as 0), text by its characters, so the same label hashes alike everywhere. This is the sketch approxDistinct uses on split tables, streams and live windows; the class lets you build, merge and ship sketches yourself. See Distinct counts.

import { DistinctSketch } from 'vectrojs';   // also 'vectrojs/browser', 'vectrojs/portable'

new DistinctSketch(registers?)

An empty sketch, or one over a Uint8Array of 4,096 registers (used as it is, not copied). Throws a RangeError for another length. The registers are the registers property.

sketch.add(value)

Adds a number or a string (anything else is turned into a string). NaN, null and undefined are skipped. Returns the sketch.

sketch.merge(other)

Merges another sketch into this one, which then estimates the distinct values of both. Returns this sketch.

sketch.estimate()

The estimated number of distinct values, a whole number.

sketch.toBytes()

A copy of the registers: 4,096 bytes to store or send.

DistinctSketch.fromBytes(bytes)

A sketch from bytes toBytes() gave (copied).

import { DistinctSketch } from 'vectrojs';

// two machines each see some of the visitors
const monday = new DistinctSketch();
const tuesday = new DistinctSketch();
for (let i = 0; i < 50_000; i++) monday.add(`user-${i}`);
for (let i = 30_000; i < 90_000; i++) tuesday.add(`user-${i}`);

const shipped = tuesday.toBytes();                       // 4,096 bytes
const both = DistinctSketch.fromBytes(monday.toBytes()).merge(DistinctSketch.fromBytes(shipped));
console.log(monday.estimate(), tuesday.estimate(), both.estimate(), shipped.length);   // true counts: 50,000, 60,000, 90,000

const nums = new DistinctSketch().add(1).add(1).add(-0).add(0).add(NaN).add(2.5);
console.log(nums.estimate());                            // 3: 1, 0 and 2.5

import { Engine, SplitEngine } from 'vectrojs';

// approxDistinct on a split table merges one sketch per worker
const ids = Float64Array.from({ length: 100_000 }, (_, i) => (i * 7919) % 40_000);
const split = new SplitEngine({ workers: 2 });
const t = await split.tableAsync({ id: ids });
console.log(await t.aggAsync({ approx: 'approxDistinct(id)', exact: 'countDistinct(id)' }));

const engine = new Engine();
console.log(engine.table({ id: ids }).agg({ n: 'approxDistinct(id)' }));   // exact on a normal table
await split.close();
await engine.close();