notesum.ai
Published at November 28Hashing for Sampling-Based Estimation
cs.DS
Released Date: November 28, 2024
Authors: Anders Aamand1, Ioana O. Bercea2, Jakob Bæk Tejs Houen3, Jonas Klausen1, Mikkel Thorup1
Aff.: 1University of Copenhagen; 2Kungliga Tekniska Högskolan; 3Alipes ApS
| Symbol | Definition | Description |
|---|---|---|
| Scales error probability of secondary events | ||
| 160 | Scales error probability in each layer | |
| Threshold for error probability in regular layers | ||
| First non-regular layer | ||
| Maximum number of layers with non-zero expected size (whp), where is the number of selection bits. Defined in Lemma 16. | ||
| Bound on the number of layers handled by Lemma 27 | ||
| Error probability for each layer in Lemma 27 | ||
| Stretch factor of multiplicative deviation of Theorem 12 | ||
| Total deviation of regular layers, from 4 and up (Theorem 14) | ||
| Deviation of layer (Lemma 25) | ||
| Deviation of layers through (Lemma 27) | ||
| Total deviation of non-regular layers, and above (Theorem 15) | ||
| Multiplicative term of deviation in Theorem 35 | ||
| Additive term of deviation in Theorem 35 |