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

From TCS Wiki
Jump to navigation Jump to search
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..."
 
imported>Etone
 
(10 intermediate revisions by the same user not shown)
Line 1: Line 1:
=Count Distinct Elements=
=Distinct Elements=


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


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


=== Markov and Chebyshev inequality===
= Set Membership=
 
=== Analysis of Flajolet-Martin estimator===
 
 
=Membership of Set=


== Perfect hashing==
== Perfect hashing==


=== FKS perfect hashing===
== Bloom filter ==
 
=== Cuckoo hashing===
 
==Approximate set membership==
 
=== Bloom filter ===


= Heavy Hitter=
= Frequency Estimation=


=== Count-min sketch===
== Count-min sketch==

Latest revision as of 08:31, 10 October 2017

Distinct Elements

An estimator by hashing

Flajolet-Martin algorithm

Set Membership

Perfect hashing

Bloom filter

Frequency Estimation

Count-min sketch