Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries

By Anna C. Gilbert, Yannis Kotidis, S. Muthu Muthukrishnan, Martin J. Strauss. Very Large Data Bases Conference, 2001

464 citations recorded by the source corpus.

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

How researchers see this paper

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

Citations in the corpus

The History of Histograms (abridged) (2003, methodology): “Wavelets have been used extensively for approximate answering of dieren t query types and/or in dierent environments: multidimensional aggregate queries (range-sum queries) in OLAP environments [75, 76], aggregate and non-aggregate relational queries with computations directly on the stored wavelet ”
Maintaining Stream Statistics over Sliding Windows (2002, background): “[8] considers, among other things, the problem of maintaining aged aggregates over data streams.”
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 .”
An improved data stream summary: the count-min sketch and its applications (2004, methodology): “One way to avoid the time complexity is to use range-sum random variables from [20] to quickly determine a sketch of χ(l, r), but that is expensive and still does not overcome the first drawback.”
Online outlier detection in sensor data using non-parametric models (2006, methodology): “to approximate histograms and wavelets in an online setting [18, 42, 13], previous studies have also shown that kernels are as accurate as those two techniques [23, 8].”
A review on time series data mining (2011, methodology): “Gilbert et al. (2001) adopt sketch based methods for capturing various linear projections of the data for representing data streams (i.e. wavelet transform) and approximate aggregate query.”
Rise and fall patterns of information diffusion: model and implications (2012, background): “Similarity search, indexing and pattern discovery in time sequences have also attracted huge interest [7, 14, 8, 16, 27, 38, 30, 34, 35, 28], but none of these methods specifically focused on modeling bursts.”
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].”
Fast, small-space algorithms for approximate histogram maintenance (2002, methodology): “In [6], the authors provided a O(B+ logN) space, exact algorithm for nding a B-term wavelet representation; this translates into a histogram using at most B logN buckets, preserving the error.”
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 ”
Data Streams: Models and Algorithms (Advances in Database Systems) (2006, methodology): “[17] Jin R., Agrawal G. (2005) An algorithm for in-core frequent itemset mining on streaming data.”
Efficient elastic burst detection in data streams (2003, methodology): “There are three well-known window models that are the subjects of many research projects [10, 11, 12, 22].”
Similarity estimation techniques from rounding algorithms (2002, unknown): “F [d(h(P ),h(Q))] = O(log n log log n) · EMD(P, Q).”
Issues in data stream management (2003, background): “Schema-level constraints include synchronization among timestamps in multiple streams, clustering (duplicates arrive contiguously), and ordering [9, 37, 56].”