Approximate query processing using wavelets

By Kaushik Chakrabarti, Minos N. Garofalakis, Rajeev Rastogi, Kyuseok Shim. The VLDB journal, 2001

534 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Signal Processing

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

How researchers see this paper

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

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Query Processing, Approximation, and Resource Management in a Data Stream Management System (2003, methodology): “…content (which is not always equivalent to inserting a sample operator into the query plan), using histograms [17] or compressed wavelets [11] when the synopsis is used for aggregation or even for a join [6], and using Bloom ﬁlters [4] for duplicate elimination, set difference, or set intersection.”
Online outlier detection in sensor data using non-parametric models (2006, methodology): “Estimating the Probability Density Function: There are several model estimation techniques that have been proposed in the literature, such as histograms [25, 21], wavelets [12, 18], kernel density estimators [40], and others.”
Selectivity estimation using probabilistic models (2001, methodology): “An alternative recent approach is the work of Acharya et al. [1] on join synopses, which maintains statistics for a few distinguished joins.”
Exploiting hierarchical domain structure to compute similarity (2003, background): “One such measure, popular in a variety of domains, is Earth-mover’s distance [Rubner et al. 1998; Chakrabarti et al. 2000].”
The History of Histograms (abridged) (2003, background): “…in di(cid:11)er-ent 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 coe(cid:14)-cients [14], and selection and aggregate queries over streams [28].”
Processing complex aggregate queries over data streams (2002, methodology): “proximate multi-join processing has received considerable attention in the context of approximate query answering, a very active area of database research in recent years [1, 6, 12, 19, 20, 24].”
Graph summarization with bounded error (2008, background): “There is a vast body of work on maintaining synopses like samples [13], histograms [15], and wavelets [6] to provide approximate answers to relational queries.”
Similarity search over time-series data using wavelets (2002, background): “How does the number of dimensions or features used in the indexing effect the search performance?”
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries (2001, methodology): “This small- approximation property motivated the use of wavelets in databases, for similarity search [5] as well as approximate query answering for point and range queries [26, 9, 16].”
Efficient elastic burst detection in data streams (2003, methodology): “Wavelets are heavily used in the context of data management and data mining, including selectivity estimation[17], approximate query processing[20, 5], dimensionality reduction[6] and streaming data analysis[12].”
Differential Privacy via Wavelet Transforms (2009, background): “The effectiveness of Privelet results from a novel application of wavelet transforms, a type of linear transformations that has been widely adopted for image processing [7] and approximate query processing [8], [9].”
Dimensions: why do we need a new data handling architecture for sensor networks? (2003, unknown): “In building this system, we draw from significant research in information theory [5, 6, 17], databases [7, 14], spatio-temporal data mining [18, 19], and previous work in sensor networks [11, 20].”
The design of an acquisitional query processor for sensor networks (2003, background): “[18, 9]), although these approaches typically focus on the problem of building histograms or summary structures over the streams rather than trying to preserve the (in order) signal as best as possible, which is the goal we tackle first.”
Models and issues in data stream systems (2002, background): “This approach of approximation through batch processing is attractive because it does not cause any uncertainty about the accuracy of the answer, sacriﬁcing timeliness instead.”
Evaluating window joins over unbounded streams (2003, methodology): “wavelets, sketches, histograms, and sampleshave been used in the context of online aggregation in which rapid, approximate answers are often more desirable than exact, precise answers [30][31][32][33][34][35][36][37][38][39].”
A survey of top-k query processing techniques in relational database systems (2008, unknown): “1998] and wavelets [Chakrabarti et al. 2001].”
TinyDB: an acquisitional query processing system for sensor networks (2005, background): “,[Garofalakis and Gibbons 2001; Chakrabarti et al. 2001]), although these approaches typically focus on the problem of building histograms or summary structures over the streams rather than trying to preserve the (in order) signal as best as possible, which is the goal we tackle first.”