TY - JOUR
T1 - Randomized counter-based algorithms for frequency estimation over data streams in O(loglogN) space
AU - Kakimura, Naonori
AU - Nitta, Riku
N1 - Publisher Copyright:
© 2023 Elsevier B.V.
PY - 2024/2/12
Y1 - 2024/2/12
N2 - This note studies the problem of estimating frequencies of items over data streams. We propose a simple streaming algorithm for the problem in small space complexity. Our algorithm is a counter-based algorithm with the aid of probabilistic counting. We show that our algorithm with k counters computes, with probability at least 1−δ, the estimation with relative error at most (1+ε)N/k, taking O(kloglog[Formula presented]+klog(ε−1δ−1k)+klogℓ) space in expectation, where N is the total number of items and ℓ is the number of different items.
AB - This note studies the problem of estimating frequencies of items over data streams. We propose a simple streaming algorithm for the problem in small space complexity. Our algorithm is a counter-based algorithm with the aid of probabilistic counting. We show that our algorithm with k counters computes, with probability at least 1−δ, the estimation with relative error at most (1+ε)N/k, taking O(kloglog[Formula presented]+klog(ε−1δ−1k)+klogℓ) space in expectation, where N is the total number of items and ℓ is the number of different items.
KW - Frequent items
KW - Probabilistic counting
KW - Streaming algorithms
UR - http://www.scopus.com/inward/record.url?scp=85178002337&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85178002337&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2023.114317
DO - 10.1016/j.tcs.2023.114317
M3 - Article
AN - SCOPUS:85178002337
SN - 0304-3975
VL - 984
JO - Theoretical Computer Science
JF - Theoretical Computer Science
M1 - 114317
ER -