高级算法 (Fall 2017)/Hashing and Sketching: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
Line 1: Line 1:
=Count Distinct Elements=
=Count Distinct Elements=


== First trial: an estimator by hashing ==
== An estimator by hashing ==


==Flajolet-Martin algorithm==
==Flajolet-Martin algorithm==

Revision as of 05:45, 20 September 2017

Count Distinct Elements

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