Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/89241
Title: Deterministic heavy hitters with sublinear query time
Authors: Li, Yi
Nakos, Vasileios
Keywords: Heavy Hitters
Turnstile Model
DRNTU::Science::Mathematics
Issue Date: 2018
Source: Li, Y., & Nakos, V. (2018). Deterministic heavy hitters with sublinear query time. Leibniz International Proceedings in Informatics, 18-. doi:10.4230/LIPIcs.APPROX-RANDOM.2018.18
Series/Report no.: Leibniz International Proceedings in Informatics
Abstract: 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^*(epsilon^{-1}) more than the best existing polynomial-time sketching algorithm (Nelson et al., RANDOM '12). Our approach is based on an iterative procedure, where most unrecovered heavy hitters are identified in each iteration. Although this technique has been extensively employed in the related problem of sparse recovery, this is the first time, to the best of our knowledge, that it has been used in the context of heavy hitters. Along the way we also obtain a sublinear time algorithm for the closely related problem of the l_1/l_1 compressed sensing, matching the space usage of previous (super-)linear time algorithms. In the strict turnstile model, we show that the runtime can be improved and the sketching matrix can be made strongly explicit with O(epsilon^{-2}log^3 n/log^3(1/epsilon)) rows.
URI: https://hdl.handle.net/10356/89241
http://hdl.handle.net/10220/46207
DOI: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.18
Rights: © 2018 Yi Li and Vasileios Nakos; licensed under Creative Commons License CC-BY.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
Deterministic Heavy Hitters with Sublinear Query Time.pdf545.56 kBAdobe PDFThumbnail
View/Open

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.