Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorLi, Yien
dc.contributor.authorNakos, Vasileiosen
dc.identifier.citationLi, Y., & Nakos, V. (2018). Deterministic heavy hitters with sublinear query time. Leibniz International Proceedings in Informatics, 18-. doi:10.4230/LIPIcs.APPROX-RANDOM.2018.18en
dc.description.abstractWe 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.en
dc.format.extent18 p.en
dc.relation.ispartofseriesLeibniz International Proceedings in Informaticsen
dc.rights© 2018 Yi Li and Vasileios Nakos; licensed under Creative Commons License CC-BY.en
dc.subjectHeavy Hittersen
dc.subjectTurnstile Modelen
dc.titleDeterministic heavy hitters with sublinear query timeen
dc.typeJournal Articleen
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen
dc.description.versionPublished versionen
item.fulltextWith 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

Citations 50

Updated on Dec 7, 2022

Page view(s)

Updated on Dec 8, 2022

Download(s) 50

Updated on Dec 8, 2022

Google ScholarTM




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