Attribute-based evaluation of multiple continuous queries for filtering incoming tuples of a data stream

作者：Lee Hyun Ho^*; Yun Eun Won; Lee Won Suk

来源：Information Sciences, 2008, 178(11): 2416-2432.

DOI：10.1016/j.ins.2008.01.014

• data stream
• multiple continuous queries
• selection predicate
• ASC (attribute selection construct)
• MCS (minimal cover set)
• tuple dropping ratio
• conditional selectivity

The filtering of incoming tuples of a data stream should be completed quickly and continuously, which requires strict time and space constraints. In order to guarantee these constraints, the selection predicates of continuous queries are grouped or indexed in most data stream management systems (DSMS). This paper proposes a new scheme called attribute selection construct (ASC). Given a set of continuous queries, an ASC divides the domain of an attribute of a data stream into a set of disjoint regions based on the selection predicates that are imposed on the attribute. Each region maintains the pre-computed matching results of the selection predicates. Consequently, an ASC can collectively evaluate all of its selection predicates at the same time. Furthermore, it can also monitor the overall evaluation statistics, such as its selectivity and tuple dropping ratio, dynamically. For those attributes that are employed to express the selection predicates of the queries, the processing order of their ASCs can significantly influence the overall performance of a multiple query evaluation. The evaluation sequence can be optimized by periodically capturing the run-time tuple dropping ratio of its current evaluation sequence. The performance of the proposed method is analyzed by a series of experiments to identify its various characteristics.

• 出版日期2008-6-1
• 单位安阳工学院