Part XI · Advanced Data Structures and Offline Techniques
65. Bitsets, Succinct and Probabilistic Data Structures
7 lessons•31 topics•Advanced / Expert
0 of 7 lessons published
65.01Outline
Bitsets for queries
- Java BitSet
- Boolean matrix operations
- Set intersection
- Fast subset sum
- Memory packing
65.02Outline
Bloom filters
- Hash functions
- Bit array
- False positives
- No false negatives under assumptions
- Capacity sizing
65.03Outline
Counting Bloom filter
- Counters
- Deletion support
- Counter saturation
- Dynamic variants
65.04Outline
Count-Min Sketch
- Pairwise-independent hashes overview
- Frequency estimate
- Error guarantee
- Heavy hitters
65.05Outline
HyperLogLog
- Leading-zero statistics
- Cardinality estimation
- Merge sketches
- Approximation error
65.06Outline
Succinct structures
- Rank/select
- Bitvectors
- Elias-Fano
- Wavelet matrix
- Balanced parentheses trees
65.07Outline
Hash-based string and set DS
- Cuckoo hashing
- Robin Hood hashing
- Hopscotch hashing overview
- Quotient filters overview