Tag: probabilistic-data-structures

William Pugh’s skip lists replaced rotation-based balancing with randomized levels, offering expected logarithmic search and update performance through a structure that behaves like a hierarchy of linked-list express lanes.

Burton Bloom's 1970 filter represented set membership in a compact bit array, allowing false positives but no false negatives and creating a durable space-time tradeoff used across modern storage systems.