layout: doc_page

Sketch Features Matrix

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

All sketches have a posteriori error bounds methods.

1 Integrated into Druid.
2 Spark Example Code on website. Theta Sketch is the only one we have tried in Spark, it doesn't mean other sketches cannot be used.
3 Tuple Sketch: Example Code in test/.../tuple/aninteger.
4 Theta Sketch: C++/Python has no implementaion of the Jaccard, yet.
5 Frequent Items Sketch: PostgreSQL implemented for Strings only.
6 KLL & REQ Sketch: Python implemented for both just floats and ints.
7 See Python Install Instructions

Definitions

Type

See Research/References for references in [...]

  • Cardinality/CPC Implementation and extension of [LAN17].
  • Cardinality/HLL Derivation and extension of [FFGM07]
  • Cardinality/Theta Derivation and extension of [DLRT16].
  • Cardinality/Tuple An Extension of the Theta family that adds attributes to each hash-key.
  • Quantiles/Cormode Derivation and extension of [AC+13]
  • Quantiles/KLL Derivation and extension of [KLL16].
  • Frequencies Derivation and extension of [ABL+17].
  • Sampling/Reservior Derivation and extension of [K98], Vol 2, Section 3.4.2, Algorithm R.
  • Sampling/VarOpt Derivation and extension of [CDKLT09].