[jira] [Comment Edited] (FLINK-2147) Approximate calculation of frequencies in data streams

["Stavros Kontopoulos (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/FLINK-2147?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15955103#comment-15955103 ] 

Stavros Kontopoulos edited comment on FLINK-2147 at 4/4/17 1:01 PM:
--------------------------------------------------------------------

I think Count-min sketch can be implemented in way that each task keeps a local count-min sketch as state, and as a next step it emits the frequencies after an aggregation of count-min sketches. Sketched of this type can be merged.

This could be windows based and would involve to implement custom operators. This is a high level description and may not fit exactly to the internals.

A distributed implementation here:
https://www.slideshare.net/databricks/sketching-big-data-with-spark-randomized-algorithms-for-largescale-data-analytics
https://github.com/apache/spark/pull/10911/files


was (Author: skonto):
I think Count-min sketch can be implemented in way that each task keeps a local count-min sketch as state, and as a next step it emits the frequencies after an aggregation of count-mi sketches. This could be windows based and would involve to implement custom operators. This is a high level description and may not fit exactly to the internals.

A distributed implementation here:
https://www.slideshare.net/databricks/sketching-big-data-with-spark-randomized-algorithms-for-largescale-data-analytics
https://github.com/apache/spark/pull/10911/files

> Approximate calculation of frequencies in data streams
> ------------------------------------------------------
>
>                 Key: FLINK-2147
>                 URL: https://issues.apache.org/jira/browse/FLINK-2147
>             Project: Flink
>          Issue Type: New Feature
>          Components: DataStream API
>            Reporter: Gabor Gevay
>              Labels: approximate, statistics
>
> 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.15#6346)