New sampling-based summary statistics for improving approximate query answers
Phillip B. Gibbons, Yossi Matias · Proceedings - ACM-SIGMOD International Conference on Management of Data · 1998
In large data recording and warehousing environments, it is often advantageous to provide fast, approximate answers to queries, whenever possible. Before DBMSs providing highly-accurate approximate answers can become a reality, many new techniques for summarizing data and for estimating answers from summarized data must be developed. This paper introduces two new sampling-based summary statistics, concise samples and counting samples, and presents new techniques for their fast incremental maintenance regardless of the data distribution. We quantify their advantages over standard sample views in terms of the number of additional sample points for the same view size, and hence in providing more accurate query answers. Finally, we consider their application to providing fast approximate answers to hot list queries. Our algorithms maintain their accuracy in the presence of ongoing insertions to the data warehouse.
Cited by 449 works. doi:10.1145/276304.276334 Open-access PDF
Authors
References
- Fast Algorithms for Mining Association Rules in Large Databases
- Dynamic itemset counting and implication rules for market basket data
- Random sampling with a reservoir
- Online aggregation
- Probabilistic counting algorithms for data base applications
- The space complexity of approximating the frequency moments
- Improved histograms for selectivity estimation of range predicates
- Sampling-Based Estimation of the Number of Distinct Values of an Attribute
- Fast incremental maintenance of approximate histograms
- The New Jersey Data Reduction Report.