Optimal approximations of the frequency moments of data streams

By Piotr Indyk, David P. Woodruff. Symposium on the Theory of Computing, 2005

295 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/881f6becd2db20d3edcf6e8ac0feb5ecb7ba50f6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND (2009, background): “A major influence on the foundations of massive data sets as well as a pioneer of novel techniques has been the frequency moments problem and its variants [FM85, AMS99, Ind06, BJK+02, CCFC04, IW05 ].”
Tight bounds for distributed functional monitoring (2011, methodology): “Inspired by work on sub-sampling [33], we try to estimate the number of coordinates j of magnitude in[2h, 2h+1), for eachh.”
Principal Component Analysis and Higher Correlations for Distributed Data (2013, background): “ncy moments for k ≤ 2 can be computed in polylog space, and polynomial space for k greater than a larger constant. This was improved to nearly matching bounds all k, with an upper bound of O˜(n1−2/k) [27] and the lower bound showing that the k’th frequency moment for k > 2 needs Ω(n1−2/k/logn) me”
Graph sketches: sparsification, spanners, and subgraphs (2012, methodology): “This paper also uses several techniques which are standard in streaming such as hierarchical sampling [23, 28], "0 sampling [21, 31] and sparse recovery [24].”
Estimating Renyi Entropy of Discrete Distributions (2014, background): “89], and starting with [AMS96], estimating the empirical moments of a data stream using minimum space has generated considerable interest, with the order-optimal space complexity for 2 determined in [IW05]. The broader problem of estimating smooth functionals of distributions was considered in [VV11”
Distributed low rank approximation of implicit functions of a matrix (2016, unknown): “This is related to the fact that such functions have at most quadratic growth, and we can generalize the samplers in [14], [15] from p-th powers to more general functions of at most quadratic growth, similar to the generalization of Braverman and Ostrovsky [18] to the work of Indyk and Woodruff [19]”