Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Processing set expressions over continuous update streams

Ganguly, Sumit, Garofalakis Minos, Rastogi Rajeev

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/49CC188B-8AE1-4BA1-937C-D042EA8DA49D-
Αναγνωριστικόhttp://www.cse.iitk.ac.in/users/sganguly/Sigmod03.pdf-
Γλώσσαen-
Μέγεθος12 pagesen
ΤίτλοςProcessing set expressions over continuous update streamsen
ΔημιουργόςGanguly, Sumiten
ΔημιουργόςGarofalakis Minosen
ΔημιουργόςΓαροφαλακης Μινωςel
ΔημιουργόςRastogi Rajeeven
ΕκδότηςAssociation for Computing Machineryen
ΠερίληψηThere is growing interest in algorithms for processing and querying continuous data streams (i.e., data that is seen only once in a fixed order) with limited memory resources. In its most general form, a data stream is actually an update stream, i.e., comprising data-item deletions as well as insertions. Such massive update streams arise naturally in several application domains (e.g., monitoring of large IP network installations, or processing of retail-chain transactions). Estimating the cardinality of set expressions defined over several (perhaps, distributed) update streams is perhaps one of the most fundamental query classes of interest; as an example, such a query may ask “what is the number of distinct IP source addresses seen in passing packets from both router R1 and R2 but not router R3?”. Earlier work has only addressed very restricted forms of this problem, focusing solely on the special case of insert-only streams and specific operators (e.g., union). In this paper, we propose the first space-efficient algorithmic solution for estimating the cardinality of full-fledged set expressions over general update streams. Our estimation algorithms are probabilistic in nature and 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 only small space and small processing time per update. Furthermore, our estimators never require rescanning or resampling of past stream items, regardless of the number of deletions in the stream. We also present lower bounds for the problem, demonstrating that the space usage of our estimation algorithms is within small factors of the optimal. Preliminary experimental results verify the effectiveness of our approach.en
ΤύποςΠλήρης Δημοσίευση σε Συνέδριοel
ΤύποςConference Full Paperen
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-12-01-
Ημερομηνία Δημοσίευσης2003-
Θεματική ΚατηγορίαDatabasesen
Βιβλιογραφική Αναφορά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.en

Υπηρεσίες

Στατιστικά