The space complexity of approximating the frequency moments

DOI10.1006/jcss.1997.1545zbMath0938.68153OpenAlexW2080745194WikidataQ56386814 ScholiaQ56386814MaRDI QIDQ1305928

Mario Szegedy, Yossi Matias, Noga Alon

Publication date: 22 September 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1545

zbMATH Keywords

space complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of data (68P99) Randomized algorithms (68W20)

Related Items

Robust sub-Gaussian estimation of a mean vector in nearly linear time, On finding common neighborhoods in massive graphs., Randomized OBDD-based graph algorithms, Finding frequent items in data streams, Counting distinct items over update streams, Taylor Polynomial Estimator for Estimating Frequency Moments, The Simultaneous Communication of Disjointness with Applications to Data Streams, Tight lower bounds for query processing on streaming and external memory data, Efficient algorithms for constructing $(1+\epsilon,\beta)$-spanners in the distributed and streaming models, Concentration of the collision estimator, Unnamed Item, A Statistical Analysis of Probabilistic Counting Algorithms, Query-monotonic Turing reductions, Randomized OBDD-Based Graph Algorithms, Robust estimation of $U$-statistics, Certifying equality with limited interaction, Optimal robust mean and location estimation via convex programs with respect to any pseudo-norms, Sublinear algorithms for approximating string compressibility, Streaming algorithms for multitasking scheduling with shared processing, A note on efficient aggregate queries in sensor networks, An information statistics approach to data stream and communication complexity, Robust statistical learning with Lipschitz and convex loss functions, Improved algorithms for distributed entropy monitoring, Indexing for summary queries, Empirical risk minimization for heavy-tailed losses, A contact detection algorithm for multi-sphere particles by means of two-level-grid-searching in DEM simulations, Adapting parallel algorithms to the W-stream model, with applications to graph problems, A note on randomized streaming space bounds for the longest increasing subsequence problem, Optimal tracking of distributed heavy hitters and quantiles, Robust machine learning by median-of-means: theory and practice, Mean estimation with sub-Gaussian rates in polynomial time, Continuous monitoring of distributed data streams over a time-based sliding window, Estimating hybrid frequency moments of data streams, Robust classification via MOM minimization, Symmetric norm estimation and regression on sliding windows, Know when to persist: deriving value from a stream buffer, Multiple Pass Streaming Algorithms for Learning Mixtures of Distributions in ${\mathbb R}^d$, SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS, On deterministic sketching and streaming for sparse recovery and norm estimation, Sublinear-time algorithms for counting star subgraphs via edge sampling, Optimal collapsing protocol for multiparty pointer jumping, Challenges in benchmarking stream learning algorithms with real-world data, Weak derandomization of weak algorithms: explicit versions of Yao's lemma, An efficient FPRAS type group testing procedure to approximate the number of defectives, Streaming techniques and data aggregation in networks of tiny artefacts, Communication complexity of approximate maximum matching in the message-passing model, Competitive analysis of maintaining frequent items of a stream, Sub-Gaussian estimators of the mean of a random vector, The NOF multiparty communication complexity of composed functions, Boosting distinct random sampling for basic counting on the union of distributed streams, Fingerprints for highly similar streams, Streaming pattern matching with $d$ wildcards, Frameworks for designing in-place graph algorithms, Noise dependency of algorithms for calculating fractal dimensions in digital images, Adaptive sampling for geometric problems over data streams, One-way multiparty communication lower bound for pointer jumping with applications, Statistical estimation with bounded memory, Best-order streaming model, Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable, Tracking join and self-join sizes in limited storage, Partition arguments in multiparty communication complexity, Stochastic convergence of random search methods to fixed size Pareto front approximations, Learning from MOM's principles: Le Cam's approach, Deterministic $k$-set structure, The communication requirements of efficient allocations and supporting prices, Applying approximate counting for computing the frequency moments of long data streams, Database query processing using finite cursor machines, Finding longest increasing and common subsequences in streaming data, Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression, A note on compressed sensing and the complexity of matrix multiplication, Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy, Random projections for Bayesian regression, Two improved range-efficient algorithms for $F_0$ estimation, A MOM-based ensemble method for robustness, subsampling and hyperparameter tuning, Sketching information divergences, How to catch $L_2$-heavy-hitters on sliding windows, Tradeoff lower lounds for stack machines, A general method for estimating correlated aggregates over a data stream, The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics, Hierarchical sampling from sketches: Estimating functions over data streams, Multiple pass streaming algorithms for learning mixtures of distributions in $\mathbb R^d$, Robust $k$-means clustering for distributions with two moments, Periodicity and Cyclic Shifts via Linear Sketches, Almost Optimal Explicit Johnson-Lindenstrauss Families, Tight time-space lower bounds for finding multiple collision pairs and their applications, A Note on Estimating Hybrid Frequency Moment of Data Streams, Unnamed Item, Know When to Persist: Deriving Value from a Stream Buffer, K-bMOM: A robust Lloyd-type clustering algorithm based on bootstrap median-of-means, Finite sample properties of parametric MMD estimation: robustness to misspecification and dependence, The breakdown point of the median of means tournament, Mean estimation and regression under heavy-tailed distributions: A survey, Computing (and Life) Is All about Tradeoffs, Near-optimal mean estimators with respect to general norms, On graph problems in a semi-streaming model, Streaming algorithms for extent problems in high dimensions, An estimator for matching size in low arboricity graphs with two applications, Distribution-free robust linear regression, Space-efficient estimation of statistics over sub-sampled streams, On the streaming indistinguishability of a random permutation and a random function, Randomized numerical linear algebra: Foundations and algorithms, Optimal In-place Algorithms for Basic Graph Problems, A Framework for Adversarially Robust Streaming Algorithms, Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8, Median-of-means approach for repeated measures data, Optimal (Euclidean) Metric Compression, On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing, Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity, A robust estimator of the S-Gini index for massive data, Three‐wise independent random walks can be slightly unbounded, A robust estimator of the proportional hazard transform for massive data, Non-asymptotic analysis and inference for an outlyingness induced winsorized mean, Robust distributed multicategory angle-based classification for massive data, Unnamed Item, Unnamed Item, Randomized counter-based algorithms for frequency estimation over data streams in $O(\log \log N)$ space, Statistical-computational trade-offs in tensor PCA and related problems via communication complexity, Robust supervised learning with coordinate gradient descent, Unnamed Item, Unnamed Item, On streaming algorithms for geometric independent set and clique, Mean estimation in high dimension, Unnamed Item, Unnamed Item, High Probability Frequency Moment Sketches, Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams, Continuous Monitoring of l_p Norms in Data Streams, Approximate F_2-Sketching of Valuation Functions, A Framework for In-place Graph Algorithms, Multiparty Communication Complexity of Vector–Valued and Sum–Type Functions, Fast Private Norm Estimation and Heavy Hitters, Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems, Derandomization for sliding window algorithms with strict correctness, Approximate set union via approximate randomization, Space‐efficient tracking of persistent items in a massive data stream, Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection, Unnamed Item, Depth First Search in the Semi-streaming Model, Two Party Distribution Testing: Communication and Security, Quantum Chebyshev's Inequality and Applications, Optimality of linear sketching under modular updates, Verifiable Stream Computation and Arthur--Merlin Communication, APPROXIMATING SMALLEST ENCLOSING BALLS WITH APPLICATIONS TO MACHINE LEARNING, Real-Time Streaming Multi-Pattern Search for Constant Alphabet, On Approximating Matrix Norms in Data Streams, Unnamed Item

Cites Work