EBPPS sketch for proportional-to-size sampling

Creates an EBPPS (Exact and Bounded Probabilistic Proportional-to-Size) sketch, which samples up to k items from a stream of weighted (item, weight) pairs. It is a modern alternative to classic reservoir sampling: each item's inclusion probability is proportional to its share of the total stream weight, with a tight bound on the resulting sample size.

Usage

ebpps(x = NULL, weight = NULL, k = NULL, type = NULL, bytes = NULL)

Arguments

x: Optional numeric or character vector of items to update the new sketch with.
weight: Optional weight(s) for each element of x: a single non-negative, finite number, or a vector of such values matching length(x). Defaults to 1. Cannot be set without x.
k: Maximum sample size, a single whole number in [1, 2^31 - 2]. Defaults to 256. Must not be set when bytes is supplied.
type: Item type for a fresh sketch, either "double" or "character". Defaults to the type of x (or "double" if x is not supplied). Must not be set when bytes is supplied.
bytes: Optional raw vector holding a native serialized sketch to reconstruct.

Value

An ebpps_sketch object. Key methods:

$update(x, weight = NULL): Add weighted items (mutates, returns the sketch).
$merge(other): Absorb another sketch with the same item type (mutates, returns the sketch).
$result(): The current sample as a numeric or character vector.
$k(), $n(), $cumulative_weight(), $c(), $is_empty(), $is_character(): Metadata accessors.
$summary(), $inspect(), $serialize(): Structured metadata, verbose debug output, and the native byte payload.

Details

Unlike the hash-based cardinality and frequency sketches, EBPPS retains items verbatim rather than hashing them, so the item type (numeric or character) is fixed when the sketch is created and cannot change.

At most one of x or bytes may be supplied:

Pass x to build a sketch and immediately update it with a numeric or character vector of items (optionally with weight). The item type is inferred from x unless type is supplied.
Pass bytes to reconstruct a sketch from a native serialized payload (as produced by sketch$serialize()). weight, k, and type must not be supplied alongside bytes; they are restored from the payload.
Pass neither for an empty (mutable) sketch with the given k and type.

update() silently ignores NA/NaN/NA_character_ in x (and the corresponding weight), matching the missing-value policy used across families; there is no na_rm argument.

Two sketches can only be merged with $merge() if they hold the same item type (a mismatch raises datasketches_incompatible_sketch). The merged sketch is resized to the smaller of the two inputs' configured k, matching the native implementation.

Examples

items <- 1:1000
weights <- runif(1000)
sketch <- ebpps(items, weights, k = 50)
sketch$result()
#>  [1]  851  671  428  420  432  584   86   10  775  495  582  655  705   48  523
#> [16]  570  377  195   35  108  426  731  126  952   47    5  111  265  913  698
#> [31]  630  573  235  307   82  835  895  562  238  171  690   63  812  900  404
#> [46]   46  601  743  667 1000
sketch$c()
#> [1] 50

# Round-trip through the native byte format.
restored <- ebpps(bytes = sketch$serialize())
restored$k()
#> [1] 50