This paper develops a new mathematical-statistical approach to analyze a class of Flajolet-Martin algorithms (FMa), and provides analytical confidence intervals for the number F0 of distinct elements in a stream, based on Chernoff bounds. The class of FMa has reached a significant popularity in bigdata stream learning, and the attention of the literature has mainly been based on algorithmic aspects, basically complexity optimality, while the statistical analysis of these class of algorithms has been often faced heuristically. The analysis provided here shows deep connections with mathematical special functions and with extreme value theory. The latter connection may help in explaining heuristic considerations, while the first opens many numerical issues, faced at the end of the present paper. Finally, the algorithms are tested on an anonymized real data stream and MonteCarlo simulations are provided to support our analytical choice in this context.

Analytical confidence intervals for the number of different objects in data streams / G. Aletti. - In: BIG DATA RESEARCH. - ISSN 2214-580X. - 25(2021 Jul 15), pp. 100248.1-100248.11. [10.1016/j.bdr.2021.100248]

Analytical confidence intervals for the number of different objects in data streams

G. Aletti
Primo
2021-07-15

Abstract

This paper develops a new mathematical-statistical approach to analyze a class of Flajolet-Martin algorithms (FMa), and provides analytical confidence intervals for the number F0 of distinct elements in a stream, based on Chernoff bounds. The class of FMa has reached a significant popularity in bigdata stream learning, and the attention of the literature has mainly been based on algorithmic aspects, basically complexity optimality, while the statistical analysis of these class of algorithms has been often faced heuristically. The analysis provided here shows deep connections with mathematical special functions and with extreme value theory. The latter connection may help in explaining heuristic considerations, while the first opens many numerical issues, faced at the end of the present paper. Finally, the algorithms are tested on an anonymized real data stream and MonteCarlo simulations are provided to support our analytical choice in this context.
Settore MAT/06 - Probabilita' e Statistica Matematica
Settore SECS-S/01 - Statistica
Centro di Ricerca Interdisciplinare su Modellistica Matematica, Analisi Statistica e Simulazione Computazionale per la Innovazione Scientifica e Tecnologica ADAMSS
Article (author)
File in questo prodotto:
File Dimensione Formato  
1909.11564.pdf

accesso aperto

Descrizione: Versione v2
Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 812.59 kB
Formato Adobe PDF
812.59 kB Adobe PDF Visualizza/Apri
1-s2.0-S2214579621000654-main.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 1.51 MB
Formato Adobe PDF
1.51 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/677744
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact