@techreport{TD:100277,
	att_abstract={{The massive data streams observed in network monitoring, data processing and
scientific studies are typically too large to store.  For many applications over such data, we must obtain compact summaries of the stream.  These summaries should allow accurate answering of post hoc queries with estimates which approximate the true answers over the original stream. The data often has an underlying structure which makes certain subset queries, in particular {em range queries}, more relevant than arbitrary subsets.  Applications such as access control, change detection, and heavy hitters typically involve subsets that are ranges
or unions thereof.

Random sampling is a natural summarization tool, being easy to implement and flexible to use. Known sampling methods are good for arbitrary queries but fail to optimize for the common case of range queries.   Meanwhile, specialized summarization algorithms have been proposed for range-sum queries and related problems.  These can outperform sampling giving fixed space resources, but lack
its flexibility and simplicity. Particularly, their accuracy degrades when queries span multiple ranges. 

We define new stream sampling algorithms with a smooth and tunable trade-off between accuracy on range-sum queries and arbitrary subset-sum queries.  The technical key is to relax requirements on the variance over all subsets to enable better performance on the ranges of interest. This boosts the accuracy on range queries while retaining the prime benefits of sampling, in particular flexibility and accuracy, with tail bounds having optimality guarantees. Our experimental study indicates that structure-aware summaries drastically improve range-sum accuracy with respect to state-of-the-art stream sampling algorithms and outperform deterministic methods on range-sum queries and hierarchical heavy
hitter queries.}},
	att_authors={ec1458, gc2602, nd1321},
	att_categories={C_CCF.9, C_NSS.9, C_CCF.1},
	att_copyright={{ACM}},
	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 2011 Conference {{, 2011-06-07}}.}},
	att_donotupload={},
	att_private={false},
	att_projects={},
	att_tags={Sampling,  Measurement,  Hierachies,  Streaming,  IP Flows},
	att_techdoc={true},
	att_techdoc_key={TD:100277},
	att_url={http://web1.research.att.com:81/techdocs_downloads/TD:100277_DS1_2010-11-09T17:40:31.937Z.pdf},
	author={Edith Cohen and Graham Cormode and Nicholas Duffield},
	institution={{ACM Sigmetrics 2011 Conference}},
	month={June},
	title={{Structure Aware Sampling on Data Streams}},
	year=2011,
}