NAME
Data::MinHash::Shared - shared-memory MinHash sketch (Jaccard similarity estimation, b-bit signatures)
SYNOPSIS
use Data::MinHash::Shared;
# two sketches with the same number of registers
my $a = Data::MinHash::Shared->new(undef, 256);
my $b = Data::MinHash::Shared->new(undef, 256);
$a->add($_) for @set_a; # fold each set's elements in
$b->add($_) for @set_b;
my $j = $a->similarity($b); # estimated Jaccard similarity, 0 .. 1
$a->merge($b); # $a becomes the sketch of A union B
# share a sketch across processes via a backing file
my $shared = Data::MinHash::Shared->new("/tmp/set.mh", 256);
# b-bit MinHash: estimate from only the low b bits, and export a compact signature
my $j = $a->bbit_similarity($b, 1); # corrected estimate from 1 bit per register
my $sig_a = $a->bbit_signature(1); # 256 bits = 32 bytes (vs 2 KiB full sketch)
my $sig_b = $b->bbit_signature(1);
my $j2 = Data::MinHash::Shared->bbit_similarity_of($sig_a, $sig_b, 256, 1);DESCRIPTION
A MinHash sketch in shared memory: it summarises a set as k "minimum hash" registers so that the Jaccard similarity of two sets -- the size of their intersection over the size of their union -- can be estimated from the fraction of registers that agree between their two sketches, in a fixed amount of memory independent of how many elements were added.
Each element is hashed once (XXH3-64) and mixed with each register's index, so the k registers behave like k independent min-hashes; every register keeps the smallest value it has ever seen. Two sets that share many elements keep the same minima in many registers, so agreeing_registers / k is an unbiased estimate of their Jaccard similarity. Accuracy improves with k: the standard error of the estimate is about 1/sqrt(k) (e.g. k = 256 gives roughly a 6% standard error, k = 1024 about 3%).
Because the sketch lives in a shared mapping, several processes update and read one sketch: any process that opens the same backing file, inherits the anonymous mapping across fork, or reopens a passed memfd folds into and reads the same registers. A write-preferring futex rwlock with dead-process recovery guards mutation. Elements are handled by their byte content; wide-character strings (any codepoint above 255) cause a "Wide character" croak -- encode to bytes first. Linux-only. Requires 64-bit Perl.
Two sketches must have the same number of registers to be compared or merged; similarity and merge croak on a register-count mismatch.
b-bit MinHash
b-bit MinHash (Li and Koenig) compares only the low b bits of each register instead of the full 64. Two registers whose true minima differ still collide in b bits with probability 2**-b, so the observed match fraction f is corrected to a Jaccard estimate as (f - 2**-b) / (1 - 2**-b). Small b (even b == 1) gives a good estimate for all but very high similarities, at a fraction of the storage: a b-bit signature is ceil(k * b / 8) bytes -- e.g. 64x smaller than the full sketch at b == 1 -- which makes it cheap to store or ship many finalized sketches.
Because this sketch is incremental (each register keeps a running 64-bit minimum, which the low bits alone cannot maintain), b-bit is offered as a finalization: the live sketch stays full, and you either compare two live sketches with bbit_similarity, or bbit_signature a snapshot for compact storage and later compare snapshots with bbit_similarity_of. b ranges from 1 to 64 (b == 64 is exactly the full similarity).
METHODS
Constructors
my $mh = Data::MinHash::Shared->new($path, $k, $mode);
my $mh = Data::MinHash::Shared->new(undef, $k); # anonymous
my $mh = Data::MinHash::Shared->new_memfd($name, $k);
my $mh = Data::MinHash::Shared->new_from_fd($fd);$k is the number of registers (at least 1, up to 2^24) and sets the accuracy/memory trade-off; memory is k * 8 bytes for the registers plus a fixed header. new and new_memfd croak on a $k below 1 or above 2^24. When reopening an existing file or memfd the stored $k wins and the caller's argument is ignored. An optional file mode may be passed as the last argument to new (e.g. 0660) for cross-user sharing; it defaults to 0600 (owner-only).
Building and comparing
my $changed = $mh->add($element); # 1 if a register was lowered, else 0
my $n = $mh->add_many(\@elements); # how many adds lowered a register
my $j = $mh->similarity($other); # estimated Jaccard similarity (0 .. 1)
my $j = $mh->jaccard($other); # alias for similarity
$mh->merge($other); # this sketch becomes the union's sketch
$mh->clear; # reset to the empty sketch
# b-bit MinHash (see above)
my $j = $mh->bbit_similarity($other, $b); # Jaccard from the low $b bits (b: 1..64)
my $sig = $mh->bbit_signature($b); # compact packed signature, ceil(k*b/8) bytes
my $j2 = Data::MinHash::Shared->bbit_similarity_of($sig_a, $sig_b, $k, $b); # compare snapshotsadd folds one element in and returns 1 if it lowered at least one register (so it changed the sketch), else 0. add_many folds an array reference under a single write lock. similarity (aliased jaccard) returns the estimated Jaccard similarity of the two underlying sets as a number between 0 and 1; two empty sketches are defined as similarity 1. merge updates this sketch in place to the min-hash of the union of the two sets (element-wise minimum). Both similarity and merge require $other to have the same $k and croak otherwise.
Introspection
$mh->size; # k, the number of registers
$mh->capacity; # alias for size
$mh->filled; # registers that hold a value: 0 if empty, else k
my @regs = $mh->registers; # snapshot of the k register values
$mh->stats; # { size, filled, ops, mmap_size }filled counts registers that hold a value (differ from the empty sentinel). Every add updates all k registers at once, so filled is 0 for a fresh or cleared sketch and k once any element has been added -- it is really an emptiness check rather than a fill gauge. registers returns a snapshot of the raw register values (unsigned integers) taken under the read lock -- useful for serialising or comparing sketches yourself.
Lifecycle
$mh->path; $mh->memfd; $mh->sync; $mh->unlink;sync flushes the mapping to its backing store (a no-op for anonymous and memfd sketches); unlink removes the backing file (also callable as Class->unlink($path)); path returns the backing path (undef for anonymous, memfd, or fd-reopened sketches) and memfd the backing descriptor.
SHARING ACROSS PROCESSES
The sketch lives in a shared mapping, shared the same three ways as the rest of the family: a backing file, an anonymous mapping inherited across fork, or a memfd passed to an unrelated process and reopened with new_from_fd($fd). Every process's add folds into the one shared sketch, so a fleet of workers can each stream part of a set and the merged sketch reflects them all.
SECURITY
Backing files are created with mode 0600 (owner-only) by default; pass an explicit octal mode (e.g. 0660) as the last argument to new for cross-user sharing. The file is opened with O_NOFOLLOW and O_EXCL, and the header is validated on attach. Any process granted write access is trusted not to corrupt the mapping.
CRASH SAFETY
Mutation is guarded by a futex-based write-preferring rwlock with PID-encoded ownership and dead-owner recovery. Each add is a short bounded update, so a crash leaves the sketch consistent up to the last completed operation. Limitation: PID reuse is not detected (very unlikely in practice).
Reader-slot exhaustion (slotless readers): dead-process recovery attributes a crashed lock holder's contribution through its reader-slot. The slot table holds 1024 entries (one per concurrent reader process). If more than that many reader processes share one mapping at once, a reader that cannot claim a slot proceeds "slotless" -- it still takes the read lock but leaves no per-process record. If such a slotless reader is then killed while holding the read lock, its share of the lock cannot be attributed to a dead process, so writer recovery cannot reclaim it and writers may block until the mapping is recreated. Reaching this needs more than 1024 concurrent reader processes on one mapping plus a crash in the brief read-lock window; the dead-process slot reclaim keeps the table from filling with stale entries, so in practice it is very unlikely.
SEE ALSO
Data::HyperLogLog::Shared (cardinality estimation), Data::BloomFilter::Shared (set membership), and the rest of the Data::*::Shared family.
AUTHOR
vividsnow
LICENSE
This is free software; you can redistribute it and/or modify it under the same terms as Perl itself.