Name
Abstract | ||
|---|---|---|
We consider a family of practical problems in the update data stream processing model, that is, data streams where arbitrary in- sertions and deletions of items are allowed. A typical problem is that of approximately estimating item frequencies to within relative error ǫ. This problem has ˜ O(ǫ 1) 1 upper and lower randomized space bounds. The current deterministic algorithm for the same problem requires ˜ O(ǫ 2) space. In this paper, we derive a deterministic space lower bound of ˜ O(ǫ 2). This implies similar ˜ O(ǫ 2) deterministic space bounds for a number of related problems. |
Year | Venue | Keywords |
|---|---|---|
2007 | Clinical Orthopaedics and Related Research | lower bound,process model,relative error,computational complexity |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Algebraic number,Upper and lower bounds,Omega,Probability of error,Mathematics,Computation | Journal | abs/cs/070 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sumit Ganguly | 1 | 813 | 236.01 |