# A Sampling Algebra for Aggregate Estimation

arXiv: https://arxiv.org/abs/1307.0193 · HTML: https://mlsanity.com/paper/1307.0193/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2013.

## Built on by (most cited first, 1 of 1)

- [SMART: Automatically Scaling Down Language Models with Accuracy Guarantees for Reduced Processing Fees](https://mlsanity.com/paper/2403.13835/) (2024)

## Abstract (arXiv)

As of 2005, sampling has been incorporated in all major database systems. While efficient sampling techniques are realizable, determining the accuracy of an estimate obtained from the sample is still an unresolved problem. In this paper, we present a theoretical framework that allows an elegant treatment of the problem. We base our work on generalized uniform sampling (GUS), a class of sampling methods that subsumes a wide variety of sampling techniques. We introduce a key notion of equivalence that allows GUS sampling operators to commute with selection and join, and derivation of confidence intervals. We illustrate the theory through extensive examples and give indications on how to use it to provide meaningful estimations in database systems.