高级算法 (Fall 2017)/Hashing and Sketching

From TCS Wiki
Revision as of 05:44, 20 September 2017 by imported>Etone (Created page with "=Count Distinct Elements= == First trial: an estimator by hashing == ==Flajolet-Martin algorithm== === Markov and Chebyshev inequality=== === Analysis of Flajolet-Martin...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Count Distinct Elements

First trial: an estimator by hashing

Flajolet-Martin algorithm

Markov and Chebyshev inequality

Analysis of Flajolet-Martin estimator

Membership of Set

Perfect hashing

FKS perfect hashing

Cuckoo hashing

Approximate set membership

Bloom filter

Heavy Hitter

Count-min sketch