"Approximate Query Processing Using Wavelets"
by
Kaushik Chakrabarti,
Minos Garofalakis,
Rajeev Rastogi, and
Kyuseok Shim.
Proceedings of VLDB'2000,
Cairo, Egypt, September 2000, pp. 111-122.
[** Invited to the "Best of VLDB'2000" Special Issue of
The VLDB Journal **]
Abstract
Approximate query processing has emerged as a cost-effective approach for
dealing with the huge data volumes and stringent response-time requirements
of today's decision-support systems.
Most work in this area, however, has so far been limited in its applicability
and query processing scope.
In this paper, we propose the use of multi-dimensional wavelets as an effective tool for
general-purpose approximate query processing in modern, high-dimensional applications.
Our approach is based on building wavelet-coefficient synopses of the data and
using these synopses to provide approximate answers to queries.
We develop novel query processing algorithms that operate directly on the wavelet-coefficient
synopses of relational tables, allowing us to process arbitrarily complex queries entirely
in the wavelet-coefficient domain.
This, of course, guarantees extremely fast response times since our approximate query execution
engine can do the bulk of its processing over compact sets of wavelet coefficients, essentially
postponing the expansion into relational tuples until the end-result of the query.
An extensive experimental study with synthetic as well as real-life data
sets establishes the effectiveness of our wavelet-based approach compared
to sampling and histograms.
[
camera-ready paper
(pdf)
(ps.gz)
|
journal version (in The VLDB Journal)
|
Kaushik's talk slides
(ppt.gz)
]
Copyright © 2000, VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided
that the copies are not made or distributed for direct commercial advantage, the
VLDB copyright notice and the title of the publication and its date appear, and
notice is given that copying is by permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires a fee and/or special
permission from the Endowment.