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

计算机科学 ›› 2005, Vol. 32 ›› Issue (11): 81-84.

• 软件工程与数据库技术 • 上一篇下一篇

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

邱海艳陈立军赵加奎

北京大学计算机科学与技术系,北京100871

出版日期:2018-11-17 发布日期:2018-11-17

QIU Hal-Yah, CHEN Li-Jun, ZHAO Jia-Kui （Department of Computer Science ＆ Technology,Peking University, Beijing 100871）

Online:2018-11-17 Published:2018-11-17

摘要/Abstract

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

关键词: 数据流大纲 n-of-N 等深指数划分 f-N模型维护算法指数时间复杂度空间复杂度

Abstract: Maintaining data stream synopsis is very important in DSMS. Data stream tuple is real-time, continuous and ordered （namely, aged）. Query engine needs to adjust query plan by on-line synopsis to guarantee its processing efficiency. In this paper, we propos

Key words: Data stream, Synopsis, n-of-N, Equi-Depth, Exponential partition

邱海艳陈立军赵加奎. ETHs：n-of-N模型下基于指数划分的一种数据流大纲维护算法[J]. 计算机科学, 2005, 32(11): 81-84. https://doi.org/

QIU Hal-Yah, CHEN Li-Jun, ZHAO Jia-Kui （Department of Computer Science ＆ Technology,Peking University, Beijing 100871）. [J]. Computer Science, 2005, 32(11): 81-84. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0