Better Bounds for Frequency Moments in Random-Order Streams

Simple item page
dc.creatorAndoni, Alexandr
dc.creatorMcGregor, Andrew
dc.creatorOnak, Krzysztof
dc.creatorPanigrahy, Rina
dc.date2008-08-16
dc.date.accessioned2026-07-07T09:57:01Z
dc.date.available2026-07-07T09:57:01Z
dc.descriptionEstimating frequency moments of data streams is a very well studied problem and tight bounds are known on the amount of space that is necessary and sufficient when the stream is adversarially ordered. Recently, motivated by various practical considerations and applications in learning and statistics, there has been growing interest into studying streams that are randomly ordered. In the paper we improve the previous lower bounds on the space required to estimate the frequency moments of a randomly ordered streams.
dc.description4 pages
dc.identifierhttps://arxiv.org/abs/0808.2222
dc.identifierhttp://arxiv.org/abs/0808.2222
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/167192
dc.subjectData Structures and Algorithms
dc.titleBetter Bounds for Frequency Moments in Random-Order Streams
dc.typetext

Files

Collections

arXiv