A statistical analysis of probabilistic counting algorithms

Details A statistical analysis of probabilistic counting algorithms A statistical analysis of probabilistic counting algorithms

2008-01-23

arxiv.org/abs/0801.3552v3

Statistics

Computation

19 pages, 0 figures

Scientific paper

This paper considers the problem of cardinality estimation in data stream applications. We present a statistical analysis of probabilistic counting algorithms, focusing on two techniques that use pseudo-random variates to form low-dimensional data sketches. We apply conventional statistical methods to compare probabilistic algorithms based on storing either selected order statistics, or random projections. We derive estimators of the cardinality in both cases, and show that the maximal-term estimator is recursively computable and has exponentially decreasing error bounds. Furthermore, we show that the estimators have comparable asymptotic efficiency, and explain this result by demonstrating an unexpected connection between the two approaches.

Affiliated with

Also associated with

No associations

Rating

A statistical analysis of probabilistic counting algorithms 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 A statistical analysis of probabilistic counting algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A statistical analysis of probabilistic counting algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-183543