ETHs:n-of-N模型下基于指数划分的一种数据流大纲维护算法

摘要

数据流大纲的维护对于DSMS非常重要:流数据的实时性、持续性和有序性(即,老化特性)使得查询引擎需要根据实时的概要信息自适应地调整执行计划,保持其执行效率.本文提出一种新的数据流大纲结构-ETHs,它通过指数划分方法将数据流在时间域上划分为指数区间,每个区间用具有较小空间复杂度和时间复杂度的Tiny直方图来记录区间的概要信息,使得ETHs既能够反映数据流上某些数据的衰减,又能够实现n-of-N模型下的共事计算,在εN误差范围内持续地维护最近N个元素的概要信息,具有较小的时间代价和空间代价.实验证明,ETHs是数据流上的一种较理想的大纲结构.