CR-precis: A deterministic summary structure for update data streams

Details CR-precis: A deterministic summary structure for update data streams CR-precis: A deterministic summary structure for update data streams

2006-09-07

arxiv.org/abs/cs/0609032v3

Computer Science

Data Structures and Algorithms

11 pages

Scientific paper

We present the \crprecis structure, that is a general-purpose, deterministic and sub-linear data structure for summarizing \emph{update} data streams. The \crprecis structure yields the \emph{first deterministic sub-linear space/time algorithms for update streams} for answering a variety of fundamental stream queries, such as, (a) point queries, (b) range queries, (c) finding approximate frequent items, (d) finding approximate quantiles, (e) finding approximate hierarchical heavy hitters, (f) estimating inner-products, (g) near-optimal $B$-bucket histograms, etc..

Affiliated with

Also associated with

No associations

Rating

CR-precis: A deterministic summary structure for update data streams 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 CR-precis: A deterministic summary structure for update data streams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and CR-precis: A deterministic summary structure for update data streams will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-317766