%0 Journal Article
%T ETHs:A Data Stream Synopsis Maintaining Algorithm Based on Exponential Partition in n-of-N Model<br>ETHs：n-of-N模型下基于指数划分的一种数据流大纲维护算法
%A QIU Hal-Yah
%A CHEN Li-Jun
%A ZHAO Jia-Kui
%A <br>邱海艳
%A 陈立军
%A 赵加奎
%J 计算机科学
%D 2005
%I 
%X 数据流大纲的维护对于DSMS非常重要：流数据的实时性、持续性和有序性（即，老化特性）使得查询引擎需要根据实时的概要信息自适应地调整执行计划，保持其执行效率。本文提出一种新的数据流大纲结构—ETHs，它通过指数划分方法将数据流在时间域上划分为指数区间，每个区间用具有较小空间复杂度和时间复杂度的Tiny直方图来记录区间的概要信息，使得ETHs既能够反映数据流上某些数据的衰减，又能够实现n-of-N模型下的共享计算，在dxr误差范围内持续地维护最近N个元素的概要信息，具有较小的时间代价和空间代价。实验证明，ETHs是数据流上的一种较理想的大纲结构。
%K Data stream
%K Synopsis
%K n-of-N
%K Equi-Depth
%K Exponential partition<br>数据流
%K 大纲
%K n-of-N
%K 等深
%K 指数划分
%K f-N模型
%K 维护算法
%K 指数
%K 时间复杂度
%K 空间复杂度
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=E8192CBED8A52FC2&yid=2DD7160C83D0ACED&vid=9971A5E270697F23&iid=708DD6B15D2464E8&sid=35FC3610259C2B32&eid=656F8C8401D91023&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=9