Estimating the εapproximate quantiles or ranks of a stream is a fundamental task in data monitoring. Given a stream x_1,..., x_n from a universe \mathcalU with total order, an additiveerror quantile sketch \mathcalM allows us to approximate the rank of any query y\in \mathcalU up to additive ε n error. In 2001, Greenwald and Khanna gave a deterministic algorithm (GK sketch) that solves the εapproximate quantiles estimation problem using O(ε^1 łog(ε n)) space \citegreenwald2001space ; recently, this algorithm was shown to be optimal by Cormode and Vesleý in 2020 \citecormode2020tight. However, due to the intricacy of the GK sketch and its analysis, oversimplified versions of the algorithm are implemented in practical applications, often without any known theoretical guarantees. In fact, it has remained an open question whether the GK sketch can be simplified while maintaining the optimal space bound. In this paper, we resolve this open question by giving a simplified deterministic algorithm that stores at most (2 + o(1))ε^1 łog (ε n) elements and solves the additiveerror quantile estimation problem; as a side benefit, our algorithm achieves a smaller constant factor than the \frac11 2 ε^1 łog(ε n) space bound in the original GK sketch~\citegreenwald2001space. Our algorithm features an easier analysis and still achieves the same optimal asymptotic space complexity as the original GK sketch. Lastly, our simplification enables an efficient data structure implementation, with a worstcase runtime of O(łog(1/ε) + łog łog (ε n)) perelement for the ordinary εapproximate quantile estimation problem. Also, for the related weighted'' quantile estimation problem, we give efficient data structures for our simplified algorithm which guarantee a worstcase perelement runtime of O(łog(1/ε) + łog łog (ε W_n/w_\textrmmin )), achieving an improvement over the previous upper bound of \citeassadi2023generalizing.
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Free, publiclyaccessible full text available May 10, 2025

Etessami, Kousha ; Feige, Uriel ; Puppis, Gabriele (Ed.)We give the first pseudorandom generators with sublinear seed length for the following variants of readonce branching programs (roBPs): 1) First, we show there is an explicit PRG of seed length O(log²(n/ε)log(n)) fooling unboundedwidth unordered permutation branching programs with a single accept state, where n is the length of the program. Previously, [LeePyneVadhan RANDOM 2022] gave a PRG with seed length Ω(n) for this class. For the ordered case, [HozaPyneVadhan ITCS 2021] gave a PRG with seed length Õ(log n ⋅ log 1/ε). 2) Second, we show there is an explicit PRG fooling unboundedwidth unordered regular branching programs with a single accept state with seed length Õ(√{n ⋅ log 1/ε} log 1/ε). Previously, no nontrivial PRG (with seed length less than n) was known for this class (even in the ordered setting). For the ordered case, [BogdanovHozaPrakriyaPyne CCC 2022] gave an HSG with seed length Õ(log n ⋅ log 1/ε). 3) Third, we show there is an explicit PRG fooling width w adaptive branching programs with seed length O(log n ⋅ log² (nw/ε)). Here, the branching program can choose an input bit to read depending on its current state, while it is guaranteed that on any input x ∈ {0,1}ⁿ, the branching program reads each input bit exactly once. Previously, no PRG with a nontrivial seed length is known for this class. We remark that there are some functions computable by constantwidth adaptive branching programs but not by subexponentialwidth unordered branching programs. In terms of techniques, we indeed show that the ForbesKelley PRG (with the right parameters) from [ForbesKelley FOCS 2018] already fools all variants of roBPs above. Our proof adds several new ideas to the original analysis of ForbesKelly, and we believe it further demonstrates the versatility of the ForbesKelley PRG.more » « less

Naor, Seffi ; Buchbinder, Niv (Ed.)