probe-maplets

v1.0.0

Published

a month ago

Approximate key-value maplets on top of probe-filters — value aggregation with filter-level space efficiency

0High
0Medium
0Low

jdvorak

maplet adaptive-quotient probabilistic-map point-maplet range-maplet spatial-maplet temporal-maplet

probe-maplets

probe-maplets — approximate key-value data structures on top of probe-filters. Maplets pair an approximate filter with companion value storage, returning merged values instead of booleans.

npm install probe-filters probe-maplets

import {
  MultiMaplet, PointMaplet, RangeMaplet, SpatialMaplet, TemporalMaplet,
  MAPLET_MERGE_OPERATORS,
} from 'probe-maplets';

Maplets extend approximate membership filters with value aggregation. Where a filter answers "does key k exist?", a maplet answers "what value is associated with key k?" — using the same space-efficient storage as filters.

Based on Time To Replace Your Filter: How Maplets Simplify System Design (arXiv:2510.05518). The filter prunes empty queries; a companion Map provides exact value aggregation.

Architecture

Maplet
├── Filter (approximate)
│   ├── PointMaplet → PointFilter
│   ├── RangeMaplet → RangeFilter
│   ├── SpatialMaplet → SpatialFilter
│   └── TemporalMaplet → TemporalFilter
└── Values Map (exact)
    └── key → encoded value state

The filter returns false ⇒ maplet returns null (no false negatives for key presence). The values Map stores encoded domain values and applies merge/subtract semantics on update.

Value domains

Every maplet is parameterized by a value domain that defines merge semantics:

| Domain | Merge | Delete | Use case | |--------|-------|--------|----------| | path-enum | least common ancestor | key-only removal | hierarchical labels, routing | | interned-set | set union | set difference | multi-valued attributes, permissions | | numeric-add | addition | subtraction | counters, metrics, event rates |

Custom domains are supported via options.valueDomain — implement encode, decode, merge, subtract, isIdentity, and onFalsePositive.

CONFIGURATION

All maplet constructors accept a valueDomainType string and an optional filterOptions object forwarded to the underlying filter.

PointMaplet(options)

new PointMaplet({
  valueDomainType: 'path-enum',        // 'path-enum' | 'interned-set' | 'numeric-add'
  valueDomain: customDomain,           // Custom domain implementation
  filterOptions: {                     // Forwarded to PointFilter
    initialCapacity: 1024,
    fingerprintSize: 14,
  },
})

RangeMaplet(options)

Same options as PointMaplet; filterOptions forwarded to RangeFilter.

SpatialMaplet(options)

Same options; filterOptions forwarded to SpatialFilter (bitsPerCoordinate, coordinateSystem, etc.).

TemporalMaplet(options)

Same options; filterOptions forwarded to TemporalFilter (bucketDurationMs, retentionDurationMs, etc.).

MultiMaplet(options)

new MultiMaplet({
  valueDomainType: 'path-enum',
  valueDomain: customDomain,           // Shared across all sub-maplets
  pointOptions: { ... },
  rangeOptions: { ... },
  spatialOptions: { ... },
  temporalOptions: { ... },
})

MultiMaplet composes all four maplet types with a shared value domain. Individual sub-maplets can be disabled via point: false, range: false, etc.

API

PointMaplet

insert(key, value)       → void         Insert with value (merged on duplicate)
query(key)               → domainValue  Merged value, or null if key absent
delete(key[, value])     → boolean      Subtract value from domain state
rejuvenate(key)          → boolean      Move key to newer fingerprint
enumerateKeys()          → [{key, value}] All stored key-value pairs
mergeFrom(other, op)     → this         MAPLET_MERGE_OPERATORS.UNION | REPLACE
getStats()               → object       Filter statistics
serialize()              → ArrayBuffer  Filter + values Map + domain state
static deserialize(buffer)

RangeMaplet

insert(key, value)                 → void
queryRange(start, end)             → domainValue  Aggregated value for interval
delete(key[, value])               → boolean      Value removed from Map only
adaptFalsePositive(start, end)     → boolean
enumerateRange(start, end)         → [{key, value}]
mergeFrom(other, op)               → this
getStats() / serialize() / static deserialize(buffer)

SpatialMaplet

insert(point, value)               → void         [x, y] with value
query(point)                       → domainValue
queryBox(min, max)                 → domainValue  Aggregated value in bounding box
querySpatial(relation, min, max)   → domainValue  intersects/contains/beside/etc.
querySpatialWitness(relation, m, M)→ {point, value} | null
adaptFalsePositiveBox(min, max)    → boolean
mergeFrom(other, op) / getStats() / serialize() / static deserialize(buffer)

relation values: 'intersects', 'contains', 'within', 'beside', 'northof', 'southof', 'eastof', 'westof'.

TemporalMaplet

insertAt(key, timestampMs, value)              → void
queryWithinLast(key, durationMs[, nowMs])      → domainValue
queryAgo(key, ageMs, toleranceMs[, nowMs])     → domainValue
queryBetweenAges(key, minAgeMs, maxAgeMs[, nowMs]) → domainValue
adaptFalsePositiveWithinLast(key, dur[, now])  → boolean
adaptFalsePositiveAgo(key, age, tol[, now])    → boolean
adaptFalsePositiveBetweenAges(key, min, max[, now]) → boolean
mergeFrom(other, op) / getStats() / serialize() / static deserialize(buffer)

MultiMaplet

MultiMaplet exposes the same methods as each sub-maplet via the MultiFilter facade pattern:

set(key, value) / get(key) / has(key) / remove(key)            Point
setRangeKey(key, value) / getRange(start, end) / hasRange(...)  Range
setSpatialPoint(point, value) / getBox(min, max) / hasBox(...)  Spatial
setTemporalKey(key, ts, value) / getWithinLast(key, dur)        Temporal
adaptFalsePositive(query, kind)              kind ∈ {'point','range','spatial','temporal'}
mergeFrom(other, operator)                   MAPLET_MERGE_OPERATORS.UNION | REPLACE
enumerateKeys()                              All point keys
serialize() / static deserialize(buffer)

MERGE SEMANTICS

Same-key merge

Inserting the same key with a different value merges the two values using the domain's merge function:

const mm = new MultiMaplet({ valueDomainType: 'path-enum' });
mm.set('k', 'building/house');
mm.set('k', 'building/apartment');
mm.get('k');  // 'building' — LCA('building/house', 'building/apartment')

const mm = new MultiMaplet({ valueDomainType: 'numeric-add' });
mm.set('k', 5);
mm.set('k', 3);
mm.get('k');  // 8

const mm = new MultiMaplet({ valueDomainType: 'interned-set' });
mm.set('k', ['A', 'B']);
mm.set('k', ['B', 'C']);
mm.get('k');  // ['A', 'B', 'C']

Instance merge (UNION)

Two maplet instances merge key-by-key, translating values between interner tables:

const a = new MultiMaplet({ valueDomainType: 'path-enum' });
a.set('shared', 'building/house');

const b = new MultiMaplet({ valueDomainType: 'path-enum' });
b.set('shared', 'building/office');

a.mergeFrom(b, MAPLET_MERGE_OPERATORS.UNION);
a.get('shared');  // 'building'

Instance merge (REPLACE)

REPLACE overwrites values. Both maplets must share the same domain type.

CROSS-MODAL QUERIES

MultiMaplet merges values across maplet types when the same key appears in multiple modes:

const mm = new MultiMaplet({ valueDomainType: 'numeric-add' });
mm.set('metric:k1', 10);            // point
mm.setRangeKey(42, 5);              // range (aggregate for all keys in partition)
mm.setSpatialPoint([7, 7], 3);      // spatial
mm.setTemporalKey('event:tx', ts, 2); // temporal

mm.get('metric:k1');                // 10 (point only)
mm.getRange(40, 50);                // 5 (range only)
mm.getBox([6, 6], [8, 8]);          // 3 (spatial only)

Each maplet queries its own filter + values Map independently; the facade dispatches to the appropriate sub-maplet.

SERIALIZATION

All maplet types serialize to ArrayBuffer with the filter binary, values Map entries, and domain interner state:

[magic]
  [filter binary]
  [domain state: interner tables]
  [values: key count][for each: key length + key bytes + encoded value]

Domain state (interner tables for path-enum and interned-set) is shared across sub-maplets in the MultiMaplet format, avoiding redundant storage.

const buf = pointMaplet.serialize();
const clone = PointMaplet.deserialize(buf);

const buf = multiMaplet.serialize();
const clone = MultiMaplet.deserialize(buf);

EXAMPLES

k-mer counting

Count genomic k-mers natively — no separate Bloom filter + hash table. One insertion touches one structure.

const kmers = new PointMaplet({ valueDomainType: 'numeric-add' });
kmers.insert('ACGT', 1);   // first sighting
kmers.insert('ACGT', 1);   // count → 2
kmers.insert('TGCA', 1);

kmers.query('ACGT');  // 2
kmers.query('TGCA');  // 1
kmers.query('GGGG');  // null — never seen

LSM storage engine — SSTable routing

Replace per-SSTable Bloom filters with one maplet per level. A single query finds which SSTable holds the key, eliminating N filter probes.

const level = new PointMaplet({ valueDomainType: 'interned-set' });

// Flush: keys from SSTable-0 and SSTable-1 merged into one maplet
level.insert('user:100', ['sst:0']);
level.insert('user:200', ['sst:0']);
level.insert('user:100', ['sst:1']);   // duplicate key — union

level.query('user:100');  // ['sst:0', 'sst:1'] — check both
level.query('user:200');  // ['sst:0'] — check one
level.query('user:999');  // null — skip level entirely

// Compaction: SSTable-0 obsoleted — subtract its keys
level.delete('user:100', ['sst:0']);
level.delete('user:200', ['sst:0']);
level.query('user:100');  // ['sst:1']
level.query('user:200');  // null — key gone from level

Genomic sequence search

Map each k-mer to a bit vector of experiments that contain it. One query returns all matching experiments — no tree traversal, exact results.

// 8 experiments indexed; bit 0 = exp-0, bit 1 = exp-1, etc.
const index = new PointMaplet({ valueDomainType: 'interned-set' });

index.insert('ACGT', [0, 3, 7]);   // exps 0,3,7 contain ACGT
index.insert('TGCA', [0, 1, 2]);   // exps 0,1,2 contain TGCA

index.query('ACGT');  // [0, 1, 2, 3, 7] — merge with prior
// ... query transcript's k-mers and intersect experiment sets

Web cache peer discovery

Instead of querying each peer's Bloom filter, one maplet query returns the set of peers caching a URL.

const peers = new PointMaplet({ valueDomainType: 'interned-set' });
peers.insert('http://example.com/a', ['peer:1', 'peer:3']);
peers.insert('http://example.com/b', ['peer:2']);

peers.query('http://example.com/a');  // ['peer:1', 'peer:3']
peers.query('http://example.com/b');  // ['peer:2']
peers.query('http://example.com/c');  // null — fetch from origin

// Peer-3 evicts a URL
peers.delete('http://example.com/a', ['peer:3']);
peers.query('http://example.com/a');  // ['peer:1']

Event recency with counters

const events = new TemporalMaplet({ valueDomainType: 'numeric-add' });
events.insertAt('request:GET', Date.now(), 1);
events.insertAt('request:GET', Date.now(), 1);
events.insertAt('request:GET', Date.now() - 30_000, 1);
events.queryWithinLast('request:GET', 60_000);  // 3

Geo-fenced alert zones

const alerts = new SpatialMaplet({ valueDomainType: 'path-enum', filterOptions: { bitsPerCoordinate: 12 } });
alerts.insert([34.05, -118.24], 'alert/critical/fire');     // LA fire zone
alerts.insert([34.06, -118.23], 'alert/critical/flood');    // LA flood zone
alerts.insert([40.71, -74.00],  'alert/warning/storm');     // NY storm zone

alerts.query([34.06, -118.23]);                              // 'alert/critical/flood'
alerts.queryBox([34.0, -118.3], [34.1, -118.2]);            // 'alert/critical' — any hazard in LA box
alerts.queryBox([40.0, -75.0], [41.0, -73.0]);              // 'alert/warning/storm'
alerts.queryBox([0, -180], [90, 180]);                       // 'alert' — LCA of all active alerts

Game engine — kill counters with rollback

Track kills per player with numeric-add. Approximate counts are fine for this; the adaptive delete ensures anti-cheat rollbacks don't leave stale state.

const kills = new PointMaplet({ valueDomainType: 'numeric-add' });
kills.insert('player:42', 1);   // +1 kill
kills.insert('player:42', 3);   // +3 (multi-kill)
kills.query('player:42');       // 4

// Anti-cheat rollback: a flagged kill is subtracted
kills.delete('player:42', 2);
kills.query('player:42');       // 2

// Player leaves — full reset
kills.delete('player:42');
kills.query('player:42');       // null — key removed from filter too

Game engine — spatial interest management

Entities move every tick. Insert positions into a SpatialMaplet, remove old ones, and query boxes to find candidates for exact collision checks before adapting stale keepsake boxes.

const world = new SpatialMaplet({
    valueDomainType: 'interned-set',
    filterOptions: { bitsPerCoordinate: 14 },
});

// Tick: insert current positions
world.insert([1523, 871],  ['entity:1']);
world.insert([1600, 900],  ['entity:2']);

// Entity-1 moves — remove old, insert new
world.delete([1523, 871],  ['entity:1']);
world.insert([1530, 875],  ['entity:1']);

// Interest query: entities near player at (1525, 870)
world.queryBox([1425, 770], [1625, 970]);  // ['entity:1', 'entity:2']

// Entity-1 despawns — fully remove
world.delete([1530, 875], ['entity:1']);

// Stale kept-boxes from removed entities → adapt
world.adaptFalsePositiveBox([1425, 770], [1625, 970]);

Published

Vulnerabilities

Links

Maintainers

Keywords

Readme

probe-maplets

Architecture

Value domains

CONFIGURATION

PointMaplet(options)

RangeMaplet(options)

SpatialMaplet(options)

TemporalMaplet(options)

MultiMaplet(options)

API

PointMaplet

RangeMaplet

SpatialMaplet

TemporalMaplet

MultiMaplet

MERGE SEMANTICS

Same-key merge

Instance merge (UNION)

Instance merge (REPLACE)

CROSS-MODAL QUERIES

SERIALIZATION

EXAMPLES

k-mer counting

LSM storage engine — SSTable routing

Genomic sequence search

Web cache peer discovery

Event recency with counters

Geo-fenced alert zones

Game engine — kill counters with rollback

Game engine — spatial interest management

SEE ALSO