att_abstract={{Random sampling is a powerful tool for working with large data. Queries over the full
dataset are replaced by approximate queries over the smaller (and hence easier to store and manipulate) sample. The sample constitutes a flexible summary that supports a wide class of queries. But in many applications, datasets are modified with time, and it is desirable to update samples without requiring access to the full underlying datasets. In this paper, we introduce and analyze novel techniques for sampling over dynamic data, modeled as a stream of modifications to weights associated with each key.

While sampling schemes designed for stream applications can often readily accommodate positive updates to the dataset, much less is known for the case of negative updates, where weights are reduced or items deleted altogether. We primarily consider the turnstile model of streams, and extend classic schemes to incorporate negative updates. Perhaps surprisingly, the modifications to handle negative updates turn out to be natural and seamless extensions of the well-known original positive update-only algorithms. We show that they produce unbiased estimators, and relate their performance to the behavior of corresponding algorithms on insert-only streams with different parameters. A careful analysis is necessitated, in order to account for the fact that sampling choices for one key now depend on the choices made for other keys.}},
	att_authors={gc2602, ec1458, nd1321},
	att_categories={C_CCF.1, C_CCF.9, C_NSS.9, C_IIS.2},
	att_copyright_notice={{(c) ACM, 2011. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM SIGMETRICS{{, 2012-06-30}}.
	author={Graham Cormode and Edith Cohen and Nicholas Duffield},
	institution={{ACM SIGMETRICS}},
	title={{Don’t Let The Negatives Bring You Down:
Algorithms for Sampling from Streams of Signed Updates}},