Distinct counting with a self-learning bitmap

Details Distinct counting with a self-learning bitmap Distinct counting with a self-learning bitmap

2011-07-08

arxiv.org/abs/1107.1697v1

Statistics

Computation

Journal of the American Statistical Association (accepted)

Scientific paper

Counting the number of distinct elements (cardinality) in a dataset is a fundamental problem in database management. In recent years, due to many of its modern applications, there has been significant interest to address the distinct counting problem in a data stream setting, where each incoming data can be seen only once and cannot be stored for long periods of time. Many probabilistic approaches based on either sampling or sketching have been proposed in the computer science literature, that only require limited computing and memory resources. However, the performances of these methods are not scale-invariant, in the sense that their relative root mean square estimation errors (RRMSE) depend on the unknown cardinalities. This is not desirable in many applications where cardinalities can be very dynamic or inhomogeneous and many cardinalities need to be estimated. In this paper, we develop a novel approach, called self-learning bitmap (S-bitmap) that is scale-invariant for cardinalities in a specified range. S-bitmap uses a binary vector whose entries are updated from 0 to 1 by an adaptive sampling process for inferring the unknown cardinality, where the sampling rates are reduced sequentially as more and more entries change from 0 to 1. We prove rigorously that the S-bitmap estimate is not only unbiased but scale-invariant. We demonstrate that to achieve a small RRMSE value of $\epsilon$ or less, our approach requires significantly less memory and consumes similar or less operations than state-of-the-art methods for many common practice cardinality scales. Both simulation and experimental studies are reported.

Affiliated with

Also associated with

No associations

Rating

Distinct counting with a self-learning bitmap does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distinct counting with a self-learning bitmap, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distinct counting with a self-learning bitmap will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-222691