Optimal Approximations of the Frequency Moments

Please use this identifier to cite or link to this item: http://dspace.mediu.edu.my:8181/xmlui/handle/1721.1/6741

Full metadata record

DC Field	Value	Language
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	-
Appears in Collections:	MIT Items

Files in This Item:

There are no files associated with this item.

DSpace JSPUI