VarOpt sketch for variance-optimal sampling and subset-sum estimation

Creates a VarOpt sketch, which samples up to k items from a stream of weighted (item, weight) pairs. It is designed for minimum-variance estimation of subset sums: $estimate_subset_sum() estimates the total weight of all stream items matching a predicate, using only the retained sample.

Usage

varopt(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

A varopt_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).
$samples(): A data frame of retained items and their estimated weights.
$estimate_subset_sum(predicate): Estimated total weight of stream items matching predicate, with lower_bound and upper_bound.
$k(), $n(), $num_samples(), $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, VarOpt 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(), or combined with varopt_union(), if they hold the same item type (a mismatch raises datasketches_incompatible_sketch). Both operations resize the result for the larger of the two inputs' configured k.

Examples

items <- 1:1000
weights <- runif(1000)
sketch <- varopt(items, weights, k = 50)
sketch$samples()
#>    item   weight
#> 1   945 10.38281
#> 2   948 10.38281
#> 3   818 10.38281
#> 4   442 10.38281
#> 5   934 10.38281
#> 6   526 10.38281
#> 7   591 10.38281
#> 8    67 10.38281
#> 9    50 10.38281
#> 10  287 10.38281
#> 11   97 10.38281
#> 12  774 10.38281
#> 13  858 10.38281
#> 14  977 10.38281
#> 15  771 10.38281
#> 16  637 10.38281
#> 17  184 10.38281
#> 18   78 10.38281
#> 19  107 10.38281
#> 20  847 10.38281
#> 21   18 10.38281
#> 22  618 10.38281
#> 23  203 10.38281
#> 24  464 10.38281
#> 25  474 10.38281
#> 26  571 10.38281
#> 27  849 10.38281
#> 28  351 10.38281
#> 29  472 10.38281
#> 30   40 10.38281
#> 31  963 10.38281
#> 32  790 10.38281
#> 33  488 10.38281
#> 34  427 10.38281
#> 35  494 10.38281
#> 36  513 10.38281
#> 37  108 10.38281
#> 38  170 10.38281
#> 39  992 10.38281
#> 40  758 10.38281
#> 41  688 10.38281
#> 42  848 10.38281
#> 43  584 10.38281
#> 44   41 10.38281
#> 45  917 10.38281
#> 46  804 10.38281
#> 47  538 10.38281
#> 48  990 10.38281
#> 49    1 10.38281
#> 50  330 10.38281
sketch$estimate_subset_sum(\(x) x <= 500)
#> $lower_bound
#> [1] 165.5012
#> 
#> $estimate
#> [1] 238.8046
#> 
#> $upper_bound
#> [1] 314.6228
#> 
#> $total_weight
#> [1] 519.1403
#> 

# Round-trip through the native byte format.
restored <- varopt(bytes = sketch$serialize())
identical(restored$samples(), sketch$samples())
#> [1] TRUE