Answering ad-hoc continuous aggregate queries over data streams using Dynamic Prefix Aggregate Tree

Abstract

In a Data Stream Management System (DSMS), data is received with a high speed and it has a high volume. Normally, data stream processing has real-time requirements and needs one-pass algorithms. On the other hand, DSMSs have limited memory capacity. Thus, approximate answers might be used in most of data stream applications. The need for aggregate functions is a common feature of both the traditional databases and the data streams, that are also used as a solution for summarizing the massive data received from data streams. In this paper, a method for answering Ad-hoc Continuous Aggregate Queries over data streams is employed that is uses aDynamic Prefix Aggregate Tree. As each tuple from data stream arrives, the required data is stored as a tree structure and used when applying the aggregate functions. Also, it is important that all phases of tree management including tree construction, maintenance and application perform in an online manner. To achieve this, all of the results have to be stored. But in order to have online tree construction and maintenance, we just need to store some of the results. So, the proposed method aims to push the selected answers closer to the registered queries answers, as much as possible. It has been found out both empirically and analytically that the proposed method is more cost-effective than using the conventional Prefix Aggregate Trees, in terms of time and memory capacity.