Resizable Sketches
summary
Proves a lower bound that any one-sided dynamic approximate membership must pay about log log n bits per element at some point, and gives a matching upper bound by gradually expanding hashed ranges to reach n log(1/ε) + n log log n bits; implements the idea as a practical Infinifilter/LF filter with near-constant query time. Presents simple expandable Misra–Gries and bottom-k schemes: Misra–Gries gets √m error with √m space by phased counters, bottom-k yields additive m^{2/3} error by growing k, and deletions/turnstile cases remain open.
AI-written summary · about
chapters (7)
- 0:00Introduction
- 2:12Expandable filters theory
- 18:30Practical expandable filters
- 21:41Misra-Gries sketch
- 27:10KMV sketch for distinct elements
- 31:29Reducing sketch size
- 41:04Q&A
related talks
10mDon’t forget to sketch! Running with large datasets
39mModel Counting Meets Distinct Estimation
33mLinear and sublinear algorithms for graphlet sampling
45mMost of the Time It Works Every Time: The Mindset Behind Using Probabilistic Data Structures
42mMergeable Summaries and the Data Sketches Library
25mErasure-Resilient Sublinear-Time Graph Algorithms
57mQuery Optimization and Evaluation 1: Output Size Bounds and Information Theory
01h 00mCount-min Sketch to Infinity