On Frequency Estimation and Detection of Heavy Hitters in Data Streams
A stream can be thought of as a very large set of data, sometimes even infinite, which arrives sequentially and must be processed without the possibility of being stored. In fact, the memory available to the algorithm is limited and it is not possible to store the whole stream of data which is inste...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-09-01
|
| Series: | Future Internet |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-5903/12/9/158 |
| _version_ | 1797553254784040960 |
|---|---|
| author | Federica Ventruto Marco Pulimeno Massimo Cafaro Italo Epicoco |
| author_facet | Federica Ventruto Marco Pulimeno Massimo Cafaro Italo Epicoco |
| author_sort | Federica Ventruto |
| collection | DOAJ |
| description | A stream can be thought of as a very large set of data, sometimes even infinite, which arrives sequentially and must be processed without the possibility of being stored. In fact, the memory available to the algorithm is limited and it is not possible to store the whole stream of data which is instead scanned upon arrival and summarized through a succinct data structure in order to maintain only the information of interest. Two of the main tasks related to data stream processing are frequency estimation and heavy hitter detection. The frequency estimation problem requires estimating the frequency of each item, that is the number of times or the weight with which each appears in the stream, while heavy hitter detection means the detection of all those items with a frequency higher than a fixed threshold. In this work we design and analyze ACMSS, an algorithm for frequency estimation and heavy hitter detection, and compare it against the state of the art AS<span style="font-variant: small-caps;">ketch</span> algorithm. We show that, given the same budgeted amount of memory, for the task of frequency estimation our algorithm outperforms AS<span style="font-variant: small-caps;">ketch</span> with regard to accuracy. Furthermore, we show that, under the assumptions stated by its authors, AS<span style="font-variant: small-caps;">ketch</span> may not be able to report all of the heavy hitters whilst ACMSS will provide with high probability the full list of heavy hitters. |
| first_indexed | 2024-03-10T16:13:46Z |
| format | Article |
| id | doaj.art-9bd2653c640d482b8e2805a9885a1b2b |
| institution | Directory Open Access Journal |
| issn | 1999-5903 |
| language | English |
| last_indexed | 2024-03-10T16:13:46Z |
| publishDate | 2020-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Future Internet |
| spelling | doaj.art-9bd2653c640d482b8e2805a9885a1b2b2023-11-20T14:16:13ZengMDPI AGFuture Internet1999-59032020-09-0112915810.3390/fi12090158On Frequency Estimation and Detection of Heavy Hitters in Data StreamsFederica Ventruto0Marco Pulimeno1Massimo Cafaro2Italo Epicoco3Dpartment of Engineering for Innovation, University of Salento, 73100 Lecce, ItalyDpartment of Engineering for Innovation, University of Salento, 73100 Lecce, ItalyDpartment of Engineering for Innovation, University of Salento, 73100 Lecce, ItalyDpartment of Engineering for Innovation, University of Salento, 73100 Lecce, ItalyA stream can be thought of as a very large set of data, sometimes even infinite, which arrives sequentially and must be processed without the possibility of being stored. In fact, the memory available to the algorithm is limited and it is not possible to store the whole stream of data which is instead scanned upon arrival and summarized through a succinct data structure in order to maintain only the information of interest. Two of the main tasks related to data stream processing are frequency estimation and heavy hitter detection. The frequency estimation problem requires estimating the frequency of each item, that is the number of times or the weight with which each appears in the stream, while heavy hitter detection means the detection of all those items with a frequency higher than a fixed threshold. In this work we design and analyze ACMSS, an algorithm for frequency estimation and heavy hitter detection, and compare it against the state of the art AS<span style="font-variant: small-caps;">ketch</span> algorithm. We show that, given the same budgeted amount of memory, for the task of frequency estimation our algorithm outperforms AS<span style="font-variant: small-caps;">ketch</span> with regard to accuracy. Furthermore, we show that, under the assumptions stated by its authors, AS<span style="font-variant: small-caps;">ketch</span> may not be able to report all of the heavy hitters whilst ACMSS will provide with high probability the full list of heavy hitters.https://www.mdpi.com/1999-5903/12/9/158data stream miningheavy hittersfrequency estimationsketches |
| spellingShingle | Federica Ventruto Marco Pulimeno Massimo Cafaro Italo Epicoco On Frequency Estimation and Detection of Heavy Hitters in Data Streams Future Internet data stream mining heavy hitters frequency estimation sketches |
| title | On Frequency Estimation and Detection of Heavy Hitters in Data Streams |
| title_full | On Frequency Estimation and Detection of Heavy Hitters in Data Streams |
| title_fullStr | On Frequency Estimation and Detection of Heavy Hitters in Data Streams |
| title_full_unstemmed | On Frequency Estimation and Detection of Heavy Hitters in Data Streams |
| title_short | On Frequency Estimation and Detection of Heavy Hitters in Data Streams |
| title_sort | on frequency estimation and detection of heavy hitters in data streams |
| topic | data stream mining heavy hitters frequency estimation sketches |
| url | https://www.mdpi.com/1999-5903/12/9/158 |
| work_keys_str_mv | AT federicaventruto onfrequencyestimationanddetectionofheavyhittersindatastreams AT marcopulimeno onfrequencyestimationanddetectionofheavyhittersindatastreams AT massimocafaro onfrequencyestimationanddetectionofheavyhittersindatastreams AT italoepicoco onfrequencyestimationanddetectionofheavyhittersindatastreams |