Optimal quantile estimation: beyond the comparison model. Gupta, M., Singhal, M., & Wu, H. April, 2024. arXiv:2404.03847 [cs]![Optimal quantile estimation: beyond the comparison model [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex Estimating quantiles is one of the foundational problems of data sketching. Given $n$ elements $x_1, x_2, {\}dots, x_n$ from some universe of size $U$ arriving in a data stream, a quantile sketch estimates the rank of any element with additive error at most ${\}varepsilon n$. A low-space algorithm solving this task has applications in database systems, network measurement, load balancing, and many other practical scenarios. Current quantile estimation algorithms described as optimal include the GK sketch (Greenwald and Khanna 2001) using $O({\}varepsilon{\textasciicircum}\{-1\} {\}log n)$ words (deterministic) and the KLL sketch (Karnin, Lang, and Liberty 2016) using $O({\}varepsilon{\textasciicircum}\{-1\} {\}log{\}log(1/{\}delta))$ words (randomized, with failure probability ${\}delta$). However, both algorithms are only optimal in the comparison-based model, whereas most typical applications involve streams of integers that the sketch can use aside from making comparisons. If we go beyond the comparison-based model, the deterministic q-digest sketch (Shrivastava, Buragohain, Agrawal, and Suri 2004) achieves a space complexity of $O({\}varepsilon{\textasciicircum}\{-1\}{\}log U)$ words, which is incomparable to the previously-mentioned sketches. It has long been asked whether there is a quantile sketch using $O({\}varepsilon{\textasciicircum}\{-1\})$ words of space (which is optimal as long as $n {\}leq {\}mathrm\{poly\}(U)$). In this work, we present a deterministic algorithm using $O({\}varepsilon{\textasciicircum}\{-1\})$ words, resolving this line of work.
@misc{gupta_optimal_2024,
title = {Optimal quantile estimation: beyond the comparison model},
shorttitle = {Optimal quantile estimation},
url = {http://arxiv.org/abs/2404.03847},
doi = {10.48550/arXiv.2404.03847},
abstract = {Estimating quantiles is one of the foundational problems of data sketching. Given \$n\$ elements \$x\_1, x\_2, {\textbackslash}dots, x\_n\$ from some universe of size \$U\$ arriving in a data stream, a quantile sketch estimates the rank of any element with additive error at most \${\textbackslash}varepsilon n\$. A low-space algorithm solving this task has applications in database systems, network measurement, load balancing, and many other practical scenarios. Current quantile estimation algorithms described as optimal include the GK sketch (Greenwald and Khanna 2001) using \$O({\textbackslash}varepsilon{\textasciicircum}\{-1\} {\textbackslash}log n)\$ words (deterministic) and the KLL sketch (Karnin, Lang, and Liberty 2016) using \$O({\textbackslash}varepsilon{\textasciicircum}\{-1\} {\textbackslash}log{\textbackslash}log(1/{\textbackslash}delta))\$ words (randomized, with failure probability \${\textbackslash}delta\$). However, both algorithms are only optimal in the comparison-based model, whereas most typical applications involve streams of integers that the sketch can use aside from making comparisons. If we go beyond the comparison-based model, the deterministic q-digest sketch (Shrivastava, Buragohain, Agrawal, and Suri 2004) achieves a space complexity of \$O({\textbackslash}varepsilon{\textasciicircum}\{-1\}{\textbackslash}log U)\$ words, which is incomparable to the previously-mentioned sketches. It has long been asked whether there is a quantile sketch using \$O({\textbackslash}varepsilon{\textasciicircum}\{-1\})\$ words of space (which is optimal as long as \$n {\textbackslash}leq {\textbackslash}mathrm\{poly\}(U)\$). In this work, we present a deterministic algorithm using \$O({\textbackslash}varepsilon{\textasciicircum}\{-1\})\$ words, resolving this line of work.},
urldate = {2024-06-21},
author = {Gupta, Meghal and Singhal, Mihir and Wu, Hongxun},
month = apr,
year = {2024},
note = {arXiv:2404.03847 [cs]},
keywords = {Computer Science - Data Structures and Algorithms},
}
Downloads: 0
{"_id":"g56qYqPP8GBJc94gL","bibbaseid":"gupta-singhal-wu-optimalquantileestimationbeyondthecomparisonmodel-2024","author_short":["Gupta, M.","Singhal, M.","Wu, H."],"bibdata":{"bibtype":"misc","type":"misc","title":"Optimal quantile estimation: beyond the comparison model","shorttitle":"Optimal quantile estimation","url":"http://arxiv.org/abs/2404.03847","doi":"10.48550/arXiv.2404.03847","abstract":"Estimating quantiles is one of the foundational problems of data sketching. Given $n$ elements $x_1, x_2, {\\}dots, x_n$ from some universe of size $U$ arriving in a data stream, a quantile sketch estimates the rank of any element with additive error at most ${\\}varepsilon n$. A low-space algorithm solving this task has applications in database systems, network measurement, load balancing, and many other practical scenarios. Current quantile estimation algorithms described as optimal include the GK sketch (Greenwald and Khanna 2001) using $O({\\}varepsilon{\\textasciicircum}\\{-1\\} {\\}log n)$ words (deterministic) and the KLL sketch (Karnin, Lang, and Liberty 2016) using $O({\\}varepsilon{\\textasciicircum}\\{-1\\} {\\}log{\\}log(1/{\\}delta))$ words (randomized, with failure probability ${\\}delta$). However, both algorithms are only optimal in the comparison-based model, whereas most typical applications involve streams of integers that the sketch can use aside from making comparisons. If we go beyond the comparison-based model, the deterministic q-digest sketch (Shrivastava, Buragohain, Agrawal, and Suri 2004) achieves a space complexity of $O({\\}varepsilon{\\textasciicircum}\\{-1\\}{\\}log U)$ words, which is incomparable to the previously-mentioned sketches. It has long been asked whether there is a quantile sketch using $O({\\}varepsilon{\\textasciicircum}\\{-1\\})$ words of space (which is optimal as long as $n {\\}leq {\\}mathrm\\{poly\\}(U)$). In this work, we present a deterministic algorithm using $O({\\}varepsilon{\\textasciicircum}\\{-1\\})$ words, resolving this line of work.","urldate":"2024-06-21","author":[{"propositions":[],"lastnames":["Gupta"],"firstnames":["Meghal"],"suffixes":[]},{"propositions":[],"lastnames":["Singhal"],"firstnames":["Mihir"],"suffixes":[]},{"propositions":[],"lastnames":["Wu"],"firstnames":["Hongxun"],"suffixes":[]}],"month":"April","year":"2024","note":"arXiv:2404.03847 [cs]","keywords":"Computer Science - Data Structures and Algorithms","bibtex":"@misc{gupta_optimal_2024,\n\ttitle = {Optimal quantile estimation: beyond the comparison model},\n\tshorttitle = {Optimal quantile estimation},\n\turl = {http://arxiv.org/abs/2404.03847},\n\tdoi = {10.48550/arXiv.2404.03847},\n\tabstract = {Estimating quantiles is one of the foundational problems of data sketching. Given \\$n\\$ elements \\$x\\_1, x\\_2, {\\textbackslash}dots, x\\_n\\$ from some universe of size \\$U\\$ arriving in a data stream, a quantile sketch estimates the rank of any element with additive error at most \\${\\textbackslash}varepsilon n\\$. A low-space algorithm solving this task has applications in database systems, network measurement, load balancing, and many other practical scenarios. Current quantile estimation algorithms described as optimal include the GK sketch (Greenwald and Khanna 2001) using \\$O({\\textbackslash}varepsilon{\\textasciicircum}\\{-1\\} {\\textbackslash}log n)\\$ words (deterministic) and the KLL sketch (Karnin, Lang, and Liberty 2016) using \\$O({\\textbackslash}varepsilon{\\textasciicircum}\\{-1\\} {\\textbackslash}log{\\textbackslash}log(1/{\\textbackslash}delta))\\$ words (randomized, with failure probability \\${\\textbackslash}delta\\$). However, both algorithms are only optimal in the comparison-based model, whereas most typical applications involve streams of integers that the sketch can use aside from making comparisons. If we go beyond the comparison-based model, the deterministic q-digest sketch (Shrivastava, Buragohain, Agrawal, and Suri 2004) achieves a space complexity of \\$O({\\textbackslash}varepsilon{\\textasciicircum}\\{-1\\}{\\textbackslash}log U)\\$ words, which is incomparable to the previously-mentioned sketches. It has long been asked whether there is a quantile sketch using \\$O({\\textbackslash}varepsilon{\\textasciicircum}\\{-1\\})\\$ words of space (which is optimal as long as \\$n {\\textbackslash}leq {\\textbackslash}mathrm\\{poly\\}(U)\\$). In this work, we present a deterministic algorithm using \\$O({\\textbackslash}varepsilon{\\textasciicircum}\\{-1\\})\\$ words, resolving this line of work.},\n\turldate = {2024-06-21},\n\tauthor = {Gupta, Meghal and Singhal, Mihir and Wu, Hongxun},\n\tmonth = apr,\n\tyear = {2024},\n\tnote = {arXiv:2404.03847 [cs]},\n\tkeywords = {Computer Science - Data Structures and Algorithms},\n}\n\n\n\n\n\n\n\n\n\n\n\n","author_short":["Gupta, M.","Singhal, M.","Wu, H."],"key":"gupta_optimal_2024","id":"gupta_optimal_2024","bibbaseid":"gupta-singhal-wu-optimalquantileestimationbeyondthecomparisonmodel-2024","role":"author","urls":{"Paper":"http://arxiv.org/abs/2404.03847"},"keyword":["Computer Science - Data Structures and Algorithms"],"metadata":{"authorlinks":{}},"downloads":0,"html":""},"bibtype":"misc","biburl":"https://bibbase.org/zotero/chiraaggohel","dataSources":["akApyGuSiBYkDccny"],"keywords":["computer science - data structures and algorithms"],"search_terms":["optimal","quantile","estimation","beyond","comparison","model","gupta","singhal","wu"],"title":"Optimal quantile estimation: beyond the comparison model","year":2024}