On Approximating Frequency Moments of Data Streams with Skewed Projections

Details On Approximating Frequency Moments of Data Streams with Skewed Projections On Approximating Frequency Moments of Data Streams with Skewed Projections

2008-02-06

arxiv.org/abs/0802.0802v1

Computer Science

Data Structures and Algorithms

Scientific paper

We propose skewed stable random projections for approximating the pth frequency moments of dynamic data streams (01) improves previous methods based on (symmetric) stable random projections. Our proposed method is applicable to data streams that are (a) insertion only (the cash-register model); or (b) always non-negative (the strict Turnstile model), or (c) eventually non-negative at check points. This is only a minor restriction for practical applications. Our method works particularly well when p = 1+/- \Delta and \Delta is small, which is a practically important scenario. For example, \Delta may be the decay rate or interest rate, which are usually small. Of course, when \Delta = 0, one can compute the 1th frequent moment (i.e., the sum) essentially error-free using a simple couter. Our method may be viewed as a ``genearlized counter'' in that it can count the total value in the future, taking in account of the effect of decaying or interest accruement. In a summary, our contributions are two-fold. (A) This is the first propsal of skewed stable random projections. (B) Based on first principle, we develop various statistical estimators for skewed stable distributions, including their variances and error (tail) probability bounds, and consequently the sample complexity bounds.

Affiliated with

Also associated with

No associations

Rating

On Approximating Frequency Moments of Data Streams with Skewed Projections 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 On Approximating Frequency Moments of Data Streams with Skewed Projections, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Approximating Frequency Moments of Data Streams with Skewed Projections will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-559804