Bottom-k sketches: better and more efficient estimation of aggregates

Edith Cohen, Haim Kaplan

Abstract

A Bottom-k sketch is a summary of a set of items with nonnegative weights. Each such summary allows us to compute approximate aggregates over the set of items. Bottom-k sketches are obtained by associating with each item in a ground set an independent random rank drawn from a probability distribution that depends on the weight of the item. For each subset of interest, the bottom-k sketch is the set of the k minimum ranked items and their ranks. Bottom-k sketches have numerous applications. We develop and analyze data structures and estimators for bottom-k sketches to facilitate their deployment. We develop novel estimators and algorithms that show that they are a superior alternative to other sketching methods in both efficiency of obtaining the sketches and the accuracy of the estimates derived from the sketches.
BibTeX
@inproceedings{cohen2007bottom,
  author = {Edith Cohen and Haim Kaplan},
  title = {{Bottom-k sketches: better and more efficient estimation of aggregates}},
  booktitle = {SIGMETRICS},
  year = {2007},
  doi = {10.1145/1254882.1254926},
}

Loading related content...

Figure