Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/49CC188B-8AE1-4BA1-937C-D042EA8DA49D | ||
| Year | 2003 | ||
| Type of Item | Conference Full Paper | ||
| License |
|
||
| Bibliographic Citation | S. Ganguly, M. Garofalakis and R. Rastogi, "Processing set expressions over continuous update streams", in ACM SIGMOD International Conference on Management of Data, June 2003, pp. 265-276. | ||
| Appears in Collections |
There is growing interest in algorithms for processing andquerying continuous data streams (i.e., data that is seenonly once in a fixed order) with limited memory resources.In its most general form, a data stream is actually an updatestream, i.e., comprising data-item deletions as well as insertions.Such massive update streams arise naturally in severalapplication domains (e.g., monitoring of large IP networkinstallations, or processing of retail-chain transactions).Estimating the cardinality of set expressions defined overseveral (perhaps, distributed) update streams is perhaps oneof the most fundamental query classes of interest; as an example,such a query may ask “what is the number of distinctIP source addresses seen in passing packets from both routerR1 and R2 but not router R3?”. Earlier work has only addressedvery restricted forms of this problem, focusing solelyon the special case of insert-only streams and specific operators(e.g., union). In this paper, we propose the firstspace-efficient algorithmic solution for estimating the cardinalityof full-fledged set expressions over general updatestreams. Our estimation algorithms are probabilistic in natureand rely on a novel, hash-based synopsis data structure,termed “2-level hash sketch”. We demonstrate how our 2-level hash sketch synopses can be used to provide low-error,high-confidence estimates for the cardinality of set expressions(including operators such as set union, intersection,and difference) over continuous update streams, using onlysmall space and small processing time per update. Furthermore,our estimators never require rescanning or resamplingof past stream items, regardless of the number of deletions inthe stream. We also present lower bounds for the problem,demonstrating that the space usage of our estimation algorithmsis within small factors of the optimal. Preliminaryexperimental results verify the effectiveness of our approach.
Copyright © DIAS 2013
