DocumentCode
2300292
Title
Streaming algorithms for estimating entropy
Author
Harvey, Nicholas J.A. ; Nelson, Jelani ; Onak, Krzysztof
Author_Institution
MIT CSAIL, Cambridge, MA
fYear
2008
fDate
5-9 May 2008
Firstpage
227
Lastpage
231
Abstract
We give a method for estimating the empirical Shannon entropy of a distribution in the streaming model of computation. Our approach reduces this problem to the well-studied problem of estimating frequency moments. The analysis of our approach is based on new results which establish quantitative bounds on the rate of convergence of Renyi entropy towards Shannon entropy.
Keywords
algorithm theory; entropy; estimation theory; Renyi entropy; Shannon entropy estimation; frequency moment estimation; streaming algorithm; Approximation algorithms; Computational modeling; Convergence; Distributed computing; Entropy; Frequency estimation; Quality of service; Telecommunication traffic; Web and internet services; Zinc;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Theory Workshop, 2008. ITW '08. IEEE
Conference_Location
Porto
Print_ISBN
978-1-4244-2269-2
Electronic_ISBN
978-1-4244-2271-5
Type
conf
DOI
10.1109/ITW.2008.4578656
Filename
4578656
Link To Document