Paper Info
Title
The Data Stream Space Complexity of Cascaded Norms
Abstract
We consider the problem of estimating cascaded aggregates over a matrix presented as a sequence of updates in a data stream. A cascaded aggregate P 卤Q is defined by evaluating aggregate Q repeatedly over each row of the matrix, and then evaluating aggregate P over the resulting vector of values. This problem was introduced by Cormode andMuthukrishnan, PODS, 2005 [CM]. We analyze the space complexity of estimating cascaded norms on an n 拢d matrix to within a small relative error. Let Lp denote the p-th norm, where p is a non-negative integer. We abbreviate the cascaded normLk 卤Lp by Lk,p . (1) For any constant k 赂 p 赂 2, we obtain a 1-pass e O(n1隆2/kd1隆2/p )-space algorithm for estimating Lk,p . This is optimal up to polylogarithmic factors and resolves an open question of [CM] regarding the space complexity of L4,2. We also obtain 1-pass space-optimal algorithms for estimating L1,k and Lk,1. (2)We prove a space lower bound of (n1隆1/k ) on estimating Lk,0 and Lk,1, resolving an open question due to Indyk, IITK Data StreamsWorkshop (Problem 8), 2006. We also resolve two more questions of [CM] concerning Lk,2 estimation and block heavy hitter problems. Ganguly, Bansal and Dube (FAW, 2008) claimed an e O(1)-space algorithm for estimating Lk,p for any k,p 2 [0,2]. Our lower bounds show this claimis incorrect.
Year
DOI
Venue
2009
10.1109/FOCS.2009.82
FOCS
Keywords
Field
DocType
cascaded aggregate p,aggregate p,cascaded normlk,data stream space complexity,cascaded norms,cascaded aggregate,cascaded norm,open question,constant k,space algorithm,aggregate q,space complexity,approximation algorithms,level set,computational complexity,histograms,algorithm design and analysis,relative error,estimation,lower bound
Integer,Approximation algorithm,Discrete mathematics,Combinatorics,Algorithm design,Upper and lower bounds,Data stream,Matrix (mathematics),Approximation error,Mathematics,Computational complexity theory
Conference
ISSN
Citations 
PageRank 
0272-5428
28
1.01
References 
Authors
21
2
Name
Order
Citations
PageRank
T. S. Jayram1137375.87
David P. Woodruff22156142.38