Probabilistic Streaming Data Sketches

Provides an interface to the 'Apache DataSketches' (< https://datasketches.apache.org/>) library of streaming algorithms for approximate analytics on data too large to hold or process exactly. Sketches are compact, mergeable summaries built in a single pass over a stream that answer queries such as approximate distinct counts, quantiles and ranks, frequent items and point-frequency estimates, weighted sampling, and set membership with mathematically proven error bounds. Implements Karnin-Lang-Liberty (KLL), Relative Error Quantiles (REQ), t-Digest, HyperLogLog (HLL), Compressed Probabilistic Counting (CPC), Theta, Frequent Items, Count-Min, Array of Doubles, Variance Optimal (VarOpt), Exact and Bounded Probabilistic Proportional-to-Size (EBPPS), and Bloom filter sketches, with native serialization for interoperability with other 'Apache DataSketches' implementations.


data.sketches

PackageVersion R-CMD-check coverage

data.sketches provides an R interface to the Apache DataSketches library of streaming algorithms for approximate analytics on data too large to hold or process exactly. Sketches are compact, mergeable summaries that answer queries such as approximate distinct counts, quantiles and ranks, frequent items and point-frequency estimates, weighted sampling, and set membership, within known error bounds.

The package implements, grouped by family:

Quantile sketches for approximate quantiles, ranks, CDF, and PMF:

  • kll_doubles(), kll_floats() – Karnin-Lang-Liberty (KLL) sketches.
  • req() – Relative Error Quantiles (REQ), accurate near one tail.
  • tdigest_double() – t-Digest, accurate near both tails.

Cardinality sketches for approximate distinct counting:

  • hll() – HyperLogLog (HLL).
  • cpc() – Compressed Probabilistic Counting (CPC).
  • theta() – Theta, with set operations theta_union(), theta_intersection(), theta_difference(), and theta_jaccard().

Frequency sketches for approximate frequency estimation:

  • frequent_items() – frequent items (heavy hitters) in a character stream.
  • count_min() – point estimates of item frequency, sized with count_min_suggest_num_hashes() and count_min_suggest_num_buckets().

Tuple sketches, a Theta-extension that pairs per-key value arrays with approximate distinct counting:

  • array_of_doubles() – Array of Doubles, with set operations array_of_doubles_union(), array_of_doubles_intersection(), and array_of_doubles_difference().

Sampling sketches for weighted sampling from a stream:

  • varopt() – VarOpt, for minimum-variance subset-sum estimation, with varopt_union() to combine sketches.
  • ebpps() – EBPPS (Exact and Bounded Probabilistic Proportional-to-Size), a modern alternative to reservoir sampling.

Filters for approximate set membership:

  • bloom_filter() – Bloom filter, sized with bloom_filter_suggest_num_filter_bits() and bloom_filter_suggest_num_hashes().

Installation

Install the released version from CRAN with:

install.packages("data.sketches")

Or install the development version from GitHub with pak:

pak::pak("pedrobtz/data.sketches")

Example

Build a KLL sketch from a numeric vector and query approximate quantiles and ranks:

library(data.sketches)

sketch <- kll_doubles(rnorm(10000))
sketch

sketch$quantile(c(0.25, 0.5, 0.75))
sketch$rank(c(-1, 0, 1))

Sketches are mergeable, so partial sketches built from different chunks of a stream can be combined into one:

a <- kll_doubles(rnorm(5000, mean = -2))
b <- kll_doubles(rnorm(5000, mean = 2))
a$merge(b)
a$quantile(c(0.25, 0.5, 0.75))

Sketches can be serialized to a raw vector and restored, for interoperability with other Apache DataSketches implementations:

bytes <- sketch$serialize()
restored <- kll_doubles(bytes = bytes)
restored$quantile(0.5)

Reference manual

It appears you don't have a PDF plugin for this browser. You can click here to download the reference manual.

install.packages("data.sketches")

0.1.2 by Pedro Baltazar, 9 hours ago


https://github.com/pedrobtz/data.sketches, https://pedrobtz.github.io/data.sketches/


Report a bug at https://github.com/pedrobtz/data.sketches/issues


Browse source code at https://github.com/cran/data.sketches


Authors: Pedro Baltazar [aut, cre, cph] , The Apache Software Foundation [ctb, cph] (Bundled Apache DataSketches C++ library , src/vendor/datasketches/) , Yahoo Inc. [cph] (Apache DataSketches C++ , 2015-2018 and 2021-2025) , Verizon Media [cph] (Apache DataSketches C++ , 2019-2020) , Stephan Brumme [ctb, cph] (Bundled xxhash64.h (MIT)) , Sun Microsystems , Inc. [cph] (FDLIBM log code adapted in bundled fdlibm_log.hpp) , Austin Appleby [ctb] (Bundled public-domain MurmurHash3 code) , Sean Eron Anderson [ctb] (Bundled public-domain bit-hack code in ceiling_power_of_2.hpp)


Documentation:   PDF Manual  


MIT + file LICENSE license


Imports R6, rlang

Suggests testthat

Linking to cpp11

System requirements: C++17


See at CRAN