Abstract
We initiate a broad study of classical problems in the streaming model with insertions and deletions in the setting where we allow the approximation factor α to be much larger than 1. Such algorithms can use significantly less memory than the usual setting for which α = 1+ε for an ε ∈ (0,1). We study large approximations for a number of problems in sketching and streaming, assuming that the underlying ndimensional vector has all coordinates bounded by M throughout the data stream:
1) For the ?_p norm/quasinorm, 0 < p ≤ 2, we show that obtaining a poly(n)approximation requires the same amount of memory as obtaining an O(1)approximation for any M = n^Θ(1), which holds even for randomly ordered streams or for streams in the bounded deletion model.
2) For estimating the ?_p norm, p > 2, we show an upper bound of O(n^{12/p} (log n log M)/α²) bits for an αapproximation, and give a matching lower bound for linear sketches.
3) For the ?₂heavy hitters problem, we show that the known lower bound of Ω(k log nlog M) bits for identifying (1/k)heavy hitters holds even if we are allowed to output items that are 1/(α k)heavy, provided the algorithm succeeds with probability 1O(1/n). We also obtain a lower bound for linear sketches that is tight even for constant failure probability algorithms.
4) For estimating the number ?₀ of distinct elements, we give an n^{1/t}approximation algorithm using O(tlog log M) bits of space, as well as a lower bound of Ω(t) bits, both excluding the storage of random bits, where n is the dimension of the underlying frequency vector and M is an upper bound on the magnitude of its coordinates.
5) For αapproximation to the Schattenp norm, we give nearoptimal Õ(n^{24/p}/α⁴) sketching dimension for every even integer p and every α ≥ 1, while for p not an even integer we obtain nearoptimal sketching dimension once α = Ω(n^{1/q1/p}), where q is the largest even integer less than p. The latter is surprising as it is unknown what the complexity of Schattenp norm estimation is for constant approximation; we show once the approximation factor is at least n^{1/q1/p}, we can obtain nearoptimal sketching bounds.
BibTeX  Entry
@InProceedings{li_et_al:LIPIcs.APPROX/RANDOM.2022.13,
author = {Li, Yi and Lin, Honghao and Woodruff, David P. and Zhang, Yuheng},
title = {{Streaming Algorithms with Large Approximation Factors}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {13:113:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772495},
ISSN = {18688969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17135},
URN = {urn:nbn:de:0030drops171354},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.13},
annote = {Keywords: streaming algorithms, ?\underlinep norm, heavy hitters, distinct elements}
}
Keywords: 

streaming algorithms, ?_p norm, heavy hitters, distinct elements 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) 
Issue Date: 

2022 
Date of publication: 

15.09.2022 