Optimal Approximations of the Frequency Moments

dc.creator	Indyk, Piotr
dc.creator	Woodruff, David
dc.date	2004-10-08T20:43:17Z
dc.date	2004-10-08T20:43:17Z
dc.date	2004-07-02
dc.date.accessioned	2013-10-09T02:46:44Z
dc.date.available	2013-10-09T02:46:44Z
dc.date.issued	2013-10-09
dc.identifier	AIM-2004-014
dc.identifier	http://hdl.handle.net/1721.1/6741
dc.identifier.uri	http://koha.mediu.edu.my:8181/xmlui/handle/1721
dc.description	We give a one-pass, O~(m^{1-2/k})-space algorithm for estimating the k-th frequency moment of a data stream for any real k>2. Together with known lower bounds, this resolves the main problem left open by Alon, Matias, Szegedy, STOC'96. Our algorithm enables deletions as well as insertions of stream elements.
dc.format	18 p.
dc.format	3705201 bytes
dc.format	761567 bytes
dc.format	application/postscript
dc.format	application/pdf
dc.language	en_US
dc.relation	AIM-2004-014
dc.subject	AI
dc.title	Optimal Approximations of the Frequency Moments

Files in this item

Files	Size	Format	View
There are no files associated with this item.