Paper Info
Title
Hierarchical Sampling from Sketches: Estimating Functions over Data Streams
Abstract
We present a randomized procedure named Hierarchical Sampling from Sketches (HSS) that can be used for estimating a class of functions over the frequency vector f of up- date streams of the form (S) = Pn i=1 (|fi|). We illustrate this by applying the H SS technique to design nearly space-optimal algorithms for estimating the pth moment of the frequency vector, for real p 2 and for estimating the entropy of a data stream. 3
Year
DOI
Venue
2009
10.1007/s00453-008-9260-5
Algorithmica
Keywords
Field
DocType
data streams · frequency moments · entropy · hss
Data mining,Data stream mining,Frequency moments,Of the form,Data stream,Algorithm,Optimal design,Sampling (statistics),STREAMS,Mathematics
Journal
Volume
Issue
ISSN
53
4
0178-4617
Citations 
PageRank 
References 
4
0.47
19
Authors
2
Name
Order
Citations
PageRank
Sumit Ganguly1813236.01
Lakshminath Bhuvanagiri2642.93