ETHs:A Data Stream Synopsis Maintaining Algorithm Based on Exponential Partition in n-of-N Model
ETHs：n-of-N模型下基于指数划分的一种数据流大纲维护算法

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