Data streams: algorithms and applications

By S. Muthu Muthukrishnan. ACM-SIAM Symposium on Discrete Algorithms, 2005

1,896 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/9386590554c429e80402c082e9d6a2398bcc36b3

How researchers see this paper

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

In Computational Theory and Mathematics

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Low rank approximation with entrywise l1-norm error (2017, methodology): “We also consider the turnstile streaming model [70] in which we receive positive or negative updates to its entries and wish to output a rank-k factorization at the end of the stream.”
Sketching as a Tool for Numerical Linear Algebra (2014, background): “xity, and how it can be used to prove bit lower bounds for the space complexity of linear algebra problems in the popular streaming model of computation. We refer the reader to Muthukrishnan’s survey [96] for a comprehensive overview on the streaming model. We state the deﬁnition of the model that w”
Quantitative Data Cleaning for Large Databases (2008, background): “In recent years there have been a number of approximate, one-pass heavy hitter algorithms that use limited memory; Muthukrishnan covers them in his recent survey article on data streams [Muthukrishnan, 2005].”
Ranking a stream of news (2005, background): “This is a typical situation with data streaming problems where the ﬂow of information is so overwhelming that it is unfeasible even to store the data or to perform a single (or more than one) scan operation(s) over the data (see [14] and references therein).”
Introduction to Property Testing (2017, background): “Lastly, we mention that research in the somewhat related area of “streaming algorithms” [15] has witnessed more interaction with practice (including computer networks and databases [213], compressed sensing (e.”
Data streaming algorithms for efficient and accurate estimation of flow size distribution (2004, methodology): “Data streaming [11] is concerned with processing a long stream of data items in one pass using a small working memory in order to answer a class of queries regarding the stream.”
On expressiveness and uncertainty awareness in rule-based classification for data streams (2017, neutral): “Data instances in a window can be used for the following three tasks [14,43] : 1.”
The Algorithm Design Manual (2020, methodology): “[KMS97] S. Khanna, M. Muthukrishnan, and S. Skiena.”
Graph stream algorithms: a survey (2014, background): “Most of the work on graph streams has occurred in the last decade and focuses on the semi-streaming model [27, 52].”
Beyond streams and graphs: dynamic tensor analysis (2006, background): “A recent surveys [23] have discussed many data streams algorithms.”
Fast approximation of matrix coherence and statistical leverage (2011, background): “3 Extension to Streaming Environments In this section, we consider the estimation of the leverage scores and of related statistics when the input data set is so large that an appropriate way to view the data is as a data stream (Muthukrishnan, 2005).”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “Applications of rank-structured matrices in data analysis. The machinery for working with rank-structured hierarchical matrices that we have described can be used also for the kernel matrices discussed in Section 19 that arise in machine learning and computational statistics. For instance, Ambikasar”
X-Stream: edge-centric graph processing using streaming partitions (2013, methodology): “Specific to graphs, there has been some success on stream processing using small [O(Vpolylog(V ))] space in the semi-streaming model [41], streaming just the edges, and more recently with the W-Stream model [14].”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “In learning with partially observed attributes (e.g. [22]), a simple reduction implies an Ω( ( d/k ) T ) lower bound when we are constrained to view at most k features of each example.”
Distributed data stream processing and edge computing: A survey on resource elasticity and future directions (2017, positive): “Muthukrishnan [32] classifies data streams under several models based on how their input data describes the underlying signal they represent.”
Compressed Sensing (2012, background): “Due to the unavoidable combinatorial search, this algorithm is however NP-hard [48].”