论文题目: 数据流上若干查询处理算法的研究
论文类型: 博士论文
论文专业: 软件与理论
作者: 金澈清
导师: 周傲英
关键词: 数据流模型,频繁元素,分位数,基数,连续查询,共享窗口连接
文献来源: 复旦大学
发表年度: 2005
论文摘要: 过去十年中,数据流模型在一些信息处理应用中广泛出现,这些应用包括因特网、传感器网络、网络交通监控、计算机网络安全、数据挖掘、金融监控、制造业、天文等等。和传统数据模型相比,数据流模型具有几个截然不同的特征:(1)数据总量被假定为是无限的;(2)数据到达速率非常快;(3)数据到达次序不受应用所约束;(4)除非可以保存,每个元素均只能够“看”一次。针对数据流模型的查询处理技术具有几点特殊要求。首先,该技术必须能够快速处理每一个元组,实时输出查询处理结果。其次,该技术的空间复杂度要低,因为数据流的规模被假定为是无限的而内存是有限的。再次,这类技术由于空间复杂度低、处理元组速率高,往往只能够得到近似解,但一般而言,该近似解都具备一定的精确度。最后,该技术适应性要强。数据流在某些应用中可能非常不稳定,不仅数据分布,而且流速都可能发生剧烈变化,“好”的数据流查询处理技术必须能够在各种状况下都具备良好的性能。 传统的数据处理技术很难被应用到数据流模型中去。数据库管理系统(DBMS)需要先将所有数据保存起来,再提交查询进行处理,难以满足实时应用的需求。另外一种处理技术是首先将所有数据全部载入到内存中,以随机访问的方式解决应用问题。但是由于数据流数据量远大于主机内存,该技术也不现实。这个现状迫使研究人员深入研究数据流模型,设计新的查询处理技术。 本文针对数据流查询处理中的几个基本问题进行研究,并做出了以下几点贡献: 1.如何挖掘数据流上的频繁元素是数据流研究的一个基本问题。我们提出了hCount算法来解决这个问题。该算法仅需要e/ε·ln(-M/ln ρ)个计数器,就能够估算每个元素的值,且最大误差不超过ε。我们还将hCount算法和一个空间时间索引结构(sRB-树)相结合,提出了stFreq算法,用于在空间时间流上挖掘频繁元素。该方法空间复杂度低,查询精度高。 2.估算分位数(quantile)问题也是数据流上的一个基本问题。我们提出了一种新算法,该算法仅仅需要2elog~2 M/ε·ln(-M/ln ρ)个计数器,就能够在包
论文目录:
中文摘要
英文摘要
图目录
表目录
第一章 引言
1.1 数据流模型
1.2 数据流研究的要求和挑战
1.3 数据流研究背景
1.4 主要贡献
1.5 组织结构
第二章 数据流研究进展
2.1 数据流算法
2.1.1 直方图(Histogram)
2.1.2 抽样方法(Sampling)
2.1.3 小波方法(Wavelet)
2.1.4 哈希方法(Hash)
2.1.5 基于滑动窗口模型的方法
2.2 数据流管理系统
2.2.1 数据流查询语言
2.2.2 查询处理和优化
2.2.3 适应性
2.2.4 降载
2.3 本章小结
第三章 挖掘频繁元素
3.1 问题定义
3.2 求解转盘模型问题
3.2.1 hCount算法
3.2.2 理论分析
3.2.3 hCount~*算法
3.2.4 当相异元素个数M并不是预先知道时
3.3 求解空间时间流问题
3.3.1 StFreq算法架构
3.3.2 sRB-树
3.3.3 四种构造sRB-树的方法
3.3.4 sRB-树的扩展性
3.4 实验
3.4.1 hCount与hCount~*的比较
3.4.2 hCount、hCount~*和groupTest的比较
3.4.3 真实数据集合下hCount算法的性能
3.4.4 测试hCount算法的扩展范围特性
3.4.5 stFreq查询算法的性能分析
3.4.6 sRB-树的空间复杂度验证
3.5 相关工作
3.6 本章小结
第四章 估算分位数和计算多流表达式基数
4.1 分位数问题
4.1.1 问题定义
4.1.2 hQuantile算法和eQuantile算法
4.1.3 相关工作
4.2 滑动窗口上多流表达式的基数问题
4.2.1 问题定义
4.2.2 相关工作
4.2.3 改良2级哈希梗概
4.2.4 wUnion、wDiff、wInter等新算法
4.2.5 实验
4.3 结论
第五章 共享窗口连接策略
5.1 共享窗口连接
5.2 静态调度策略
5.2.1 突发模式
5.3 适应性调度策略
5.3.1 查询图
5.3.2 AS调度策略
5.4 降载策略
5.4.1 系统框架
5.4.2 基本约束条件
5.4.3 降载策略的算法
5.4.4 误差的确定
5.5 实验
5.5.1 AS策略实验
5.5.2 降载策略实验
5.6 小结
第六章 总结
6.1 未来工作的展望
参考文献
索引
攻读博士期间发表论文
致谢
发布时间: 2005-09-19
参考文献
- [1].基于概念漂移的数据流集成分类算法研究[D]. 任思琪.湖南大学2018
- [2].数据流系统中负载管理技术应用研究[D]. 王金栋.南京航空航天大学2006
- [3].多数据流处理的关键技术研究[D]. 陈安龙.四川大学2006
- [4].数据流聚集查询和频繁模式挖掘的研究[D]. 刘学军.东南大学2006
- [5].数据流概要与数据流分析若干关键问题研究[D]. 王永利.东南大学2006
- [6].数据流聚类分析算法[D]. 曹锋.复旦大学2006
- [7].基于屏蔽/汇总技术的数据流处理算法[D]. 崇志宏.复旦大学2006
- [8].数据流上的分类算法的研究[D]. 王鹏.复旦大学2007
- [9].分布式数据流查询处理若干关键技术的研究[D]. 杨颖.东华大学2006
- [10].WEB数据挖掘研究[D]. 王勇.西北工业大学2006
相关论文
- [1].流数据查询系统结构及模式查询算法的研究[D]. 刘建伟.东华大学2005
- [2].数据流系统中负载管理技术应用研究[D]. 王金栋.南京航空航天大学2006
- [3].网络恶意数据流的检测与控制技术研究[D]. 郑军.哈尔滨工业大学2006
- [4].基于网格和密度的数据流聚类方法研究[D]. 单世民.大连理工大学2006
- [5].数据流聚集查询和频繁模式挖掘的研究[D]. 刘学军.东南大学2006
- [6].数据流概要与数据流分析若干关键问题研究[D]. 王永利.东南大学2006
- [7].数据流聚类分析算法[D]. 曹锋.复旦大学2006
- [8].数据流上的异常检测[D]. 秦首科.复旦大学2006
- [9].数据流上的分类算法的研究[D]. 王鹏.复旦大学2007
- [10].分布式数据流查询处理若干关键技术的研究[D]. 杨颖.东华大学2006