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

摘要：

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

关键词：数据流、大纲、n-of-N、等深、指数划分

所属期刊栏目：32

分类号：TP3(计算技术、计算机技术)

在线出版日期：2005-12-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：81-84