Summarizing data using bottom-k sketches
Edith Cohen, Haim Y. Kaplan · 2007
A Bottom-sketch is a summary of a set of items with nonnegative weights that supports approximate query processing. A sketch is 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 and including the k items with smallest rank value.