Fast identification of heavy hitters by cached and packed group testing

DOI10.1007/978-3-030-32686-9_17zbMATH Open1539.68088MaRDI QIDQ6536258FDOQ6536258

Authors: Yusaku Kaneta, Takeaki Uno, Hiroki Arimura 

Publication date: 19 April 2024

Recommendations

• An optimal algorithm for \(\ell_1\)-heavy hitters in insertion streams and related problems
• New algorithms for heavy hitters in data streams (invited talk)
• Beating CountSketch for heavy hitters in insertion streams
• Deterministic heavy hitters with sublinear query time
• Hierarchical Heavy Hitters with the Space Saving Algorithm

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Data structures (68P05)

Cites Work

• Finding repeated elements
• Universal classes of hash functions
• Finding frequent items in data streams
• Range majority in constant time and linear space
• Better space bounds for parameterized range majority and minority
• An improved data stream summary: the count-min sketch and its applications
• Data streams: algorithms and applications.
• Encodings for range majority queries
• Dynamic maintenance of majority information in constant time per update
• Title not available (Why is that?)
• Bit-parallel string matching under Hamming distance in \(O(n\lceil m/w\rceil)\) worst case time
• Regular expression matching with multi-strings and intervals
• Title not available (Why is that?)
• The frequent items problem, under polynomial decay, in the streaming model
• What's hot and what's not: tracking most frequent items dynamically

This page was built for publication: Fast identification of heavy hitters by cached and packed group testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6536258)