Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries

Surajit Chaudhuri, Gautam Das, and Vivek Narasayya

Abstract

The ability to approximately answer aggregation queries accurately and efficiently is of great benefit for decision support and data mining tools. In contrast to previous sampling-based studies, we treat the problem as an optimization problem whose goal is to minimize the error in answering queries in the given workload. A key novelty of our approach is that we can tailor the choice of samples to be robust even for workloads that are “similar” but not necessarily identical to the given workload. Finally, our techniques recognize the importance of taking into account the variance in the data distribution in a principled manner. We show how our solution can be implemented on a database system, and present results of extensive experiments on Microsoft SQL Server 2000 that demonstrate the superior quality of our method compared to previous work.

Details

Publication typeInproceedings
Published inSIGMOD
Pages45
NumberMSR-TR-2001-37
InstitutionMicrosoft Research
PublisherAssociation for Computing Machinery, Inc.
> Publications > A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries