Algorithms & Data Structures
the bound is a claim, and it is checkable
Depth

Series — page 2

A field says what an essay is about. A series follows one idea essay by essay — from the question that introduces it to the one that assumes all the others.
rank among the boundaries, sorted by the text before themsorted by the text after0 in the rectanglepattern "ss is un"split after 40 end with the left half0 begin with the rightEnglish-like · 2 copies of 512z = 156 · 0 crossing

Grid

  1. 1 The candidates a filter cannot avoid
  2. 2 A rectangle over a permutation
  3. 3 The operations a candidate count leaves out
  4. 4 The structure paid for before the first query
  5. 5 A bit for every bit
  6. +4 more
9 essays · indexes answered 19.90%25%50%75%100%0.36420.52,170value, logarithmicfraction of the stream at or belowrank ±2%value 19.3–21.9answered 2.9% out20,000 values · log-normal, σ = 1.2 — a latency distribution · Greenwald–Khanna, ε = 0.02rank 1.02% · value 2.9%

Rank

  1. 1 The error that is on the rank
  2. 2 A promise about the rank is not a promise about the value
  3. 3 An error measured against the answer
  4. 4 The digest that promises nothing
  5. 5 The promise that does not survive the tree
  6. +4 more
9 essays · streaming 1,00010,0000.1bits of state heldrelative errorHyperLogLog (-0.49)LogLog (-0.44)bottom-k (-0.38)50,000 distinct keys · 14 runs per point · truth counted exactlybest: 2.00% at 10,240 bits

Sketch

  1. 1 The answer that is allowed to be wrong
  2. 2 Counting past what the register holds
  3. 3 The estimate that is a median of means
  4. 4 A count that is never under
  5. 5 The items that survive k counters
  6. +4 more
9 essays · streaming —1234152abcbcbccbsolid: a transition on a character · dashed: a suffix or failure link8 states ≤ 9, 9 transitions ≤ 11

Automaton

  1. 1 Every substring, in fewer states than substrings
  2. 2 One pass for every pattern at once
  3. 3 Two states per operator
  4. 4 The exponential is in the expression
  5. 5 What a character costs on four machines
  6. +3 more
8 essays · structures decayedwindowed060120secondscount attributed to key 0half-life 4 s · window 5.77 s · burstythe same key, two questions

Decay

  1. 1 The counter with no window in it
  2. 2 The fading nobody computes
  3. 3 A decay measured from where it started
  4. 4 What a heavier tail actually buys
  5. 5 A detector that learns its own quiet
  6. +3 more
8 essays · streaming 1,00010,00010³10⁴bits · runs12481632characters in the collection · copies aboven·H₃, bitsr, runs in thetransformEnglish-like · base 512 · divergence 0n·H₃ x15.8 · r x1.00

Repeat

  1. 1 The entropy that cannot see a copy
  2. 2 The index that stores the runs
  3. 3 What is still proportional to n
  4. 4 A floor under a run count
  5. 5 The sampling that follows the runs
  6. +3 more
8 essays · text 110100257amortised 2.000256512append numbercost of that append (log scale)growth factor 2, cost = 1 write + a copy of the array when it resizes9 resizes in 512 appends

Structure

  1. 1 What amortised means
  2. 1 The tree that is a list
  3. 2 Choosing a growth factor
  4. 3 Building a heap from the bottom
  5. 4 The priority nobody supplied
  6. +3 more
8 essays · structures 01325leading-zero rank keptregister, 0 to 255estimate 7,107truth 7,368error -3.54%0 still empty256 registers × 5 bits = 1,280 bitspredicted ±6.50%

Cardinality

  1. 1 A count read off the leading zeros
  2. 2 The correction that makes it work
  3. 3 The summaries that add
  4. 4 The floor under a summary
  5. 5 The error of a difference
  6. +1 more
6 essays · streaming mean 494599th 60304,2825,4136,543comparisonsruns600 independent random inputs, n = 512worst run 1.32× the mean

Distribution

  1. 1 The words "on average" are not a number
  2. 2 What randomising the pivot buys
  3. 2 The probe formula nobody checks
  4. 3 Expected is not average
  5. 4 What derandomising costs
  6. +1 more
6 essays · wrong +1−1keys, most frequent firstΣ s(x)·f(x) = 9,034squared: 81,613,156true F2: 36,931,352121.0% outa polynomial of degree 4 · cash-register model · counts exactone register, 32 bits

Moment

  1. 1 The estimate that squares the stream
  2. 2 The independence an estimator spends
  3. 3 A sketch that is allowed to be under
  4. 4 The moments past the second
  5. 5 The keys worth counting before sampling
  6. +1 more
6 essays · streaming 50318223749516674879310811positionthe minimum12 values · depth 3answer 6 (1)

Range

  1. 1 The shape a range question is about
  2. 2 Two bits a value, and what undoes them
  3. 3 The table that fits inside a block
  4. 4 Where a crossing moved to
4 essays · structures

All essays