## Abstract

In this paper, we introduce the Significant One Counting problem. Let ε and θ be respectively some user-specified error bound and threshold. The input of the problem is a stream of bits. We need to maintain some data structure that allows us to estimate the number of 1-bits in a sliding window of size n such that whenever there are at least θn 1-bits in the window, the relative error of the estimate is guaranteed to be at most ε. When θ = 1/n, our problem becomes the Basic Counting problem proposed by Datar et al. [ACM-SIAM Symposium on Discrete Algorithms (2002), pp. 635-644]. We prove that any data structure for the Significant One Counting problem must use at least Ω(1/ε log^{2} 1/θ + log εθn) bits of memory. We also design a data structure for the problem that matches this memory bound and supports constant query and update time. Note that for fixed θ and ε, our data structure uses O(log n) bits of memory, while any data structure for the Basic Counting problem needs Ω(log^{2} n) bits in the worst case.

Original language | English |
---|---|

Pages | 724-732 |

Number of pages | 9 |

DOIs | |

Publication status | Published - 2006 |

Externally published | Yes |

Event | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: 22 Jan 2006 → 24 Jan 2006 |

### Conference

Conference | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | Miami, FL |

Period | 22/01/06 → 24/01/06 |