Tag
probabilistic-structures
- May 29, 2025 Skip Lists: Express Lanes over a Sorted Chain Layered forward pointers turn a linear scan into an expected O(log n) search, and the geometric level distribution is what makes the expected bound hold without rebalancing. data structures
- Feb 22, 2025 Composing Probabilistic Checks: Why Error Budgets Do Not Add Chaining filters and sketches multiplies false positives instead of summing them, correlation between stages breaks the union bound, and the pipeline error is dominated by the weakest stage. data structures