Streaming Quantiles Algorithms with Small Space and Update Time

Approximating quantiles and distributions over streaming data has been studied for roughly two decades now. Recently, Karnin, Lang, and Liberty proposed the first asymptotically optimal algorithm for doing so. This manuscript complements their theoretical result by providing a practical variants of...

Descripción completa

Detalles Bibliográficos
Autores principales: Ivkin, Nikita, Liberty, Edo, Lang, Kevin, Karnin, Zohar, Braverman, Vladimir
Formato: Online Artículo Texto
Lenguaje:English
Publicado: MDPI 2022
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9783260/
https://www.ncbi.nlm.nih.gov/pubmed/36559998
http://dx.doi.org/10.3390/s22249612
_version_ 1784857536096108544
author Ivkin, Nikita
Liberty, Edo
Lang, Kevin
Karnin, Zohar
Braverman, Vladimir
author_facet Ivkin, Nikita
Liberty, Edo
Lang, Kevin
Karnin, Zohar
Braverman, Vladimir
author_sort Ivkin, Nikita
collection PubMed
description Approximating quantiles and distributions over streaming data has been studied for roughly two decades now. Recently, Karnin, Lang, and Liberty proposed the first asymptotically optimal algorithm for doing so. This manuscript complements their theoretical result by providing a practical variants of their algorithm with improved constants. For a given sketch size, our techniques provably reduce the upper bound on the sketch error by a factor of two. These improvements are verified experimentally. Our modified quantile sketch improves the latency as well by reducing the worst-case update time from [Formula: see text] down to [Formula: see text].
format Online
Article
Text
id pubmed-9783260
institution National Center for Biotechnology Information
language English
publishDate 2022
publisher MDPI
record_format MEDLINE/PubMed
spelling pubmed-97832602022-12-24 Streaming Quantiles Algorithms with Small Space and Update Time Ivkin, Nikita Liberty, Edo Lang, Kevin Karnin, Zohar Braverman, Vladimir Sensors (Basel) Article Approximating quantiles and distributions over streaming data has been studied for roughly two decades now. Recently, Karnin, Lang, and Liberty proposed the first asymptotically optimal algorithm for doing so. This manuscript complements their theoretical result by providing a practical variants of their algorithm with improved constants. For a given sketch size, our techniques provably reduce the upper bound on the sketch error by a factor of two. These improvements are verified experimentally. Our modified quantile sketch improves the latency as well by reducing the worst-case update time from [Formula: see text] down to [Formula: see text]. MDPI 2022-12-08 /pmc/articles/PMC9783260/ /pubmed/36559998 http://dx.doi.org/10.3390/s22249612 Text en © 2022 by the authors. https://creativecommons.org/licenses/by/4.0/Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
spellingShingle Article
Ivkin, Nikita
Liberty, Edo
Lang, Kevin
Karnin, Zohar
Braverman, Vladimir
Streaming Quantiles Algorithms with Small Space and Update Time
title Streaming Quantiles Algorithms with Small Space and Update Time
title_full Streaming Quantiles Algorithms with Small Space and Update Time
title_fullStr Streaming Quantiles Algorithms with Small Space and Update Time
title_full_unstemmed Streaming Quantiles Algorithms with Small Space and Update Time
title_short Streaming Quantiles Algorithms with Small Space and Update Time
title_sort streaming quantiles algorithms with small space and update time
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9783260/
https://www.ncbi.nlm.nih.gov/pubmed/36559998
http://dx.doi.org/10.3390/s22249612
work_keys_str_mv AT ivkinnikita streamingquantilesalgorithmswithsmallspaceandupdatetime
AT libertyedo streamingquantilesalgorithmswithsmallspaceandupdatetime
AT langkevin streamingquantilesalgorithmswithsmallspaceandupdatetime
AT karninzohar streamingquantilesalgorithmswithsmallspaceandupdatetime
AT bravermanvladimir streamingquantilesalgorithmswithsmallspaceandupdatetime

Ejemplares similares