| 【中文题名】 | 数据流管理系统中概要数据结构算法的研究和实现 |
| 【英文题名】 | |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-3-2 |
| 【中关键词】 | 数据流管理系统,概要数据结构,Haar小波变换,X-SQL,阈值, |
| 【英关键词】 | DSMS,Abstract Data structure,Harr Wavelet Synopses,X-SQL,Thresholding Value, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>计算技术、计算机技术>计算机软件>管理程序、管理系统> |
| 【论文摘要】 |
近年来,在金融服务、网络监控、电信数据管理及传感器检测等领域中,出现了一类新的数据密集型应用。这类应用的特征是:数据以大量、快速、时变的数据流形式持续到达,所以数据不宜用持久稳定关系建模,而适合用数据流建模。论文在研究目前国际上最新的数据流管理技术的基础上,介绍了东南大学自行开发的基于硬件预处理器的数据流管理系统原型SEUSTREAM的体系结构和一种可以支持对数据流上进行持续查询的查询语言X-SQL。
在很多实际应用中,例如决策支持系统、查询优化等,用户并不需要获得确切值,而仅需要一个近似值。因此,设计单遍扫描算法(one-pass algorithm),实时地给出近似查询结果就成为数据流模型下数据处理的目标。算法的关键在于设计一个远小于数据集规模的结构,从而可以在内存中处理数据。相对于数据流的规模而言,这种名为概要数据结构(synopsis data structure)的规模至少是次线性的。
小波变换大纲作为高效的数据压缩还原技术引起了数据流领域的高度关注。论文详细介绍了哈尔小波的变换过程,并且引入了误差树的概念对这个变换过程进行了详细的分析。在此基础上实现了用哈尔小波方法生成概... |
| 【论文题纲】 |
|
摘要 |
3-4 |
|
Abstract |
4-7 |
|
第一章 数据流管理技术概述 |
7-18 |
|
1.1 数据流的出现 |
7-8 |
|
1.1.1 数据流特征 |
7 |
|
1.1.2 数据流模型 |
7-8 |
|
1.1.3 传统DBMS 处理数据流遇到的问题 |
8 |
|
1.2 数据流查询 |
8-9 |
|
1.3 数据流管理技术研究现状 |
9-12 |
|
1.3.1 STREAM 系统 |
9-10 |
|
1.3.2 Aurora 系统 |
10-11 |
|
1.3.3 TelegraphCQ 系统 |
11-12 |
|
1.3.4 国内研究情况 |
12 |
|
1.4 基于硬件预处理器的数据流管理原型系统SEUSTREAM |
12-16 |
|
1.4.1 SEUSTREAM 体系结构 |
12-13 |
|
1.4.2 连续流查询语言X-SQL |
13-16 |
|
1.5 主要研究工作和内容安排 |
16-18 |
|
第二章 生成概要数据结构的主要方法 |
18-23 |
|
2.1 数据流模型分类 |
18 |
|
2.2 生成概要数据结构的主要方法 |
18-21 |
|
2.2.1 基本窗口(basic window) |
18-19 |
|
2.2.2 直方图(histogram) |
19 |
|
2.2.3 抽样方法(sampling) |
19-20 |
|
2.2.4 小波方法(wavelet) |
20-21 |
|
2.3 基于滑动窗口的数据流处理模型 |
21 |
|
2.4 关键问题及难点 |
21-23 |
|
第三章 Haar小波方法生成数据概要 |
23-34 |
|
3.1 一维离散Haar 小波变换 |
23-27 |
|
3.2 系统总体方案 |
27-28 |
|
3.3 主要算法功能介绍 |
28-30 |
|
3.3.1 测试数据生成算法 |
28 |
|
3.3.2 小波大纲的生成 |
28 |
|
3.3.3 对小波大纲进行缩减 |
28-29 |
|
3.3.4 利用缩减后的小波大纲重构原数据流 |
29-30 |
|
3.4 小波系数阈值 |
30 |
|
3.5 实验评估及算法性能测试 |
30-33 |
|
3.5.1 小波大纲中保留元素的数量 |
30-31 |
|
3.5.2 不同阈值下的重构结果 |
31-32 |
|
3.5.3 不同阈值下重构的数据与原始数据的误差的绝对值 |
32 |
|
3.5.4 不同阈值下重构的数据与原始数据的相对误差的绝对值 |
32-33 |
|
3.6 本章小结 |
33-34 |
|
第四章 基于可变阈值小波大纲的讨论 |
34-39 |
|
4.1 固定阈值小波大纲的问题分析 |
34-35 |
|
4.2 基于概率的可变阈值的小波变换 |
35-37 |
|
4.3 改进算法的实现 |
37 |
|
4.4 实验分析 |
37-38 |
|
4.5 本章小结 |
38-39 |
|
第五章 结论与展望 |
39-41 |
|
5.1 工作总结 |
39 |
|
5.2 未来工作展望 |
39-41 |
|
致谢 |
41-42 |
|
参考文献 |
42-45 |
|
| 【DOI】 | LunWen.ID:2.2008.356840 |
