layout: doc_page

Sketch Features Matrix

Use the following table to compare the capabilities of the different sketch families.

1 Integrated into Druid
2 Example Code on website
3 Example Code in test/.../tuple/aninteger

Definitions

Type

See Research for references in [...]

  • Cardinality/FM85 Derivations of [FM85]. They include the popular HyperLogLog (HLL) Sketch as well as the Compressed Probabilistic Counting (CPC) Sketch, which has a completely different theoretical derivation and is superior to the HLL sketch in terms of accuracy per byte of storage.
  • Cardinality/Theta Derivations of [BJKST02].
  • Cardinality/Tuple An Extension of the Theta family that adds attributes to each hash-key.
  • Quantiles/Cormode Based on [AC+13]
  • Quantiles/KLL Based on [KLL16].
  • Frequencies Based on [ABL+17].
  • Sampling Two families, The simple reservoir sketch is based on Knuth, algorithm R. The VarOpt sketch is based on [CDKLT09].