Deterministic heavy hitters with sublinear query time

• Main Authors: Li, Yi, Nakos, Vasileios
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2018
• Subjects: Heavy Hitters; Turnstile Model; DRNTU::Science::Mathematics
• Online Access: https://hdl.handle.net/10356/89241; http://hdl.handle.net/10220/46207
• Institution: Nanyang Technological University

We study the classic problem of finding l_1 heavy hitters in the streaming model. In the general turnstile model, we give the first deterministic sublinear-time sketching algorithm which takes a linear sketch of length O(epsilon^{-2} log n * log^*(epsilon^{-1})), which is only a factor of log^*(epsi...