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].