Abstract: This paper targets at aggregate queries over historical data in data stream within time intervals, and proposes a novel storage model called Multi-Bloom Filters(MBF) based on Bloom Filters(BF). It uses a global bit vector to realize high efficiency of insertion and query, combines dynamically allocated local counter vectors to store historical data over different time intervals into these counter vectors. Therefore, MBF efficiently supports to store and query historical data over data stream using multiple levels of time granularities. A method of compressing space of MBF is given under the condition that the time span is very large. Analysis shows that MBF has great flexibility and supports approximate aggregate queries over historical data within time intervals, where optimal parameters of MBF are provided in term of query accuracy.

Key words: data streams, historical data, approximate aggregate queries, Bloom Filters(BF)

摘要： 针对数据流上任意时间段的历史数据的聚集查询问题，提出基于BF技术的概要存储模型MBF。采用全局比特位向量提供数据元素的快速插入和查找，结合动态分配的局部计数器向量存储不同时间段下的历史数据，使MBF支持不同时间粒度上历史数据的有效存储和高效查询，给出历史时间跨度较大情况下MBF的压缩方法以及MBF模型的参数最优化设置。理论分析证明，MBF具有较大的灵活性，能有效支持时间范围内历史数据元素的近似聚集查询。

关键词: 数据流, 历史数据, 近似聚集查询, Bloom Filters技术

CLC Number: 

• TP311.13