Bottom-k sketches

Edith Cohen, Haim KaplanACM SIGMETRICS Performance Evaluation Review 2007 · DOI

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
@article{cohen2007bottom,
  author = {Edith Cohen and Haim Kaplan},
  title = {{Bottom-k sketches}},
  journal = {ACM SIGMETRICS Performance Evaluation Review},
  year = {2007},
  doi = {10.1145/1269899.1254926},
}

Loading related content...

Figure