Data-streams and histograms

By Sudipto Guha, Nick Koudas, Kyuseok Shim. Symposium on the Theory of Computing, 2001

315 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/f42ea44e71949a39374d0211b51d77802bbb44c8

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 Computer Networks and Communications

In Signal Processing

Citations in the corpus

Data streams: algorithms and applications (2005, background): “• Building a histogram on the Time Series data stream [98].”
Models and issues in data stream systems (2002, methodology): “Guha, Koudas and Shim [43] adapted this algorithm to sorted data streams.”
Processing complex aggregate queries over data streams (2002, background): “, single-attribute) histograms and Haar wavelet decompositions [17, 15].”
Stabbing the sky: efficient skyline computation over sliding windows (2005, background): “In many applications, a data stream may be append-only [1, 9]; that is, there is no deletion of data element involved .”
Efficient decision tree construction on streaming data (2003, background): “More recently, the database community has focused on a new model of data processing, in which data arrives in the form of continuous streams [3, 4, 9, 12, 14, 16, 23, 30].”
Efficient Computation of Frequent and Top-k Elements in Data Streams (2005, background): “Problems studied in this context include approximate frequency moments [1], differences [20], distinct values estimation [22, 33, 45], bit counting [16], duplicate detection [42], approximate quantiles [28, 38, 40], histograms [30, 29], wavelet based aggregate queries [25, 41], correlated aggregate ”
Fast, small-space algorithms for approximate histogram maintenance (2002, methodology): “The algorithm of [9] provided a (1+ )-approximation preserving the number of buckets, using O(B2 logN) space and taking time O(NB2 logN).”
Finding Hierarchical Heavy Hitters in Data Streams (2003, methodology): “There has been much recent work on online algorithms for maintaining frequency distributions over a data stream including histograms [14, 15, 12] and hot items [22].”
Better streaming algorithms for clustering problems (2003, methodology): “Categories and Subject Descriptors F.2.2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity computations on discrete structures General Terms Algorithms,Theory Keywords Clustering,k-median,streaming algorithm 1.”
Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams (2003, unknown): “For instance, Datar et al. [11] give an approximate algorithm for bit counting in a sliding window .”
Clustering Data Streams: Theory and Practice (2003, background): “…in small space when the data is a stream include: frequency estimation [36], [12], norm estimation [4], [22], [44], order statistics [64], [57], [56], [30], [28], synopsis structures [26], time indexed data [25], [32], [17], [8], signal reconstructions [24], [18], [1], [33], [27], [29], [72].”
Approximate Frequency Counts over Data Streams (2012, background): “Algorithms over data streams that pertain to aggregation include approximate quantiles [MRL99, GK01], Voptimal histograms [ GKS01b ], wavelet based aggregate queries [GKMS01, MVW00], and correlated aggregate queries [GKS01a].”
Approximate join processing over data streams (2003, methodology): “For maintaining online data stream statistics, e.g., in order to compute the tuple priorities for join memory replacement, some of the recently proposed stream aggregation approaches could be applied. Recent work includes [10, 12, 14, 15 , 27].”
Maintaining Stream Statistics over Sliding Windows (2002, methodology): “While Jagadish et al. [14] address the off-line version of computing optimal histograms, Guha and Koudas [10] provide a technique for maintaining near optimal time-based histograms in an on-line fashion over streaming data.”
Matrix approximation and projective clustering via volume sampling (2006, methodology): “Algorithms for the streaming model have been designed for computing frequency moments [7], histograms [20], etc.”