flink-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Gabor Gevay (JIRA)" <j...@apache.org>
Subject [jira] [Created] (FLINK-2147) Approximate calculation of frequencies in data streams
Date Wed, 03 Jun 2015 10:07:50 GMT
Gabor Gevay created FLINK-2147:
----------------------------------

             Summary: Approximate calculation of frequencies in data streams
                 Key: FLINK-2147
                 URL: https://issues.apache.org/jira/browse/FLINK-2147
             Project: Flink
          Issue Type: Sub-task
            Reporter: Gabor Gevay
            Priority: Minor


Count-Min sketch is a hashing-based algorithm for approximately keeping track of the frequencies
of elements in a data stream. It is described by Cormode et al. in the following paper:
http://dimacs.rutgers.edu/~graham/pubs/papers/cmsoft.pdf
Note that this algorithm can be conveniently implemented in a distributed way, as described
in section 3.2 of the paper.

The paper
http://www.vldb.org/conf/2002/S10P03.pdf
also describes algorithms for approximately keeping track of frequencies, but here the user
can specify a threshold below which she is not interested in the frequency of an element.
The error-bounds are also different than the Count-min sketch algorithm.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message