Bottom-k sketches
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
@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...