Keyboard shortcuts

/ or ⌘/Ctrl K
Find a note
j / k
Next / previous section or linked note
h / l
Collapse or go to parent / expand or enter
e or Alt-click
Read a linked note here
o
Open focused note on its own
g g / G
First / last section or linked note
g h / g a
Home / all notes
g b / g t
Backlinks / table of contents
t
Cycle System, Light, Dark
? / Esc
Show / close this reference

Search: ↑/↓ or Ctrl N/P, Enter to open. Shortcuts pause while typing.

kll approximate quantiles [a2739ff5]

statistics

  • Probably what the APPROX QUANTILES in SQL is doing
  • Minimize base complexity

  • Probably approximately correct

    • Failure is okay! As long as its bounded
  • eplison and delta

  • Union bound

    • The probability of 2 events (A, B) -> probability of both of them happening is limited by the union bound
  • merability allows you to have parallelism
  • stack of compactors does not affect accuracy! shrinking is good and bounds memory usage upper bounds
  • at some point it doesn't matter because you've seen enough

  • weight provide you information about compaction, tells you how much the rank is going to move

    • symmetric changes in rank
  • repeated compaction
  • apache.github.io/datasketches-python/main/quantiles/kll.html