Bottom-k sketches: better and more efficient estimation of aggregates
Lists
Only you see this
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...