数据流环境下聚集查询的若干问题研究

来源 :北京大学 | 被引量 : 0次 | 上传用户:okdangdang
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近几年,随着网络、通信以及传感技术的发展,数据流受到普遍关注;常见的数据流包括Web访问日志数据流、股票价格信息数据流以及网络信息数据流。随着数据流越来越受关注,研究人员提出了一类新的数据模型,即数据流模型。在传统的数据库模型中,查询在静态的数据集上执行,返回查询结果后查询即告结束。在数据流模型中,查询在实时、持续、有序、无界的数据流上持续执行,当数据流中的流数据发生变化时以增量的方式对查询结果进行实时更新。由于数据流是无界的,数据流上的持续查询通常将查询数据限制在最近一段时间或最近某些流数据内,这就是数据流滑动窗口环境下的查询。由于数据流滑动窗口环境下的聚集查询在在线决策支持领域有着广泛的应用,本文对数据流滑动窗口环境下的聚集若干问题进行研究。由于数据流的流速可能非常高、流速可能呈现脉冲、数据量可能非常大以及数据流上的查询对实时性要求比较高,数据流上的查询处理和优化在提高时空性能上充满了挑战。本文首先用可加性、可减性和抽样性三个性质对聚集函数进行分类,分类结果说明了在数据流滑动窗口环境下处理特定聚集查询所能得到的空间性能最优的方法。以这个聚集函数分类为基础,本文对如下四个滑动窗口聚集查询的查询处理和优化方法有所创新,即数据流多滑动窗口环境下的最值查询、数据流滑动窗口环境下的skyline查询、数据流滑动窗口环境下的skyband查询和数据流滑动窗口环境下的集合势查询。具体地说,本文将包含如下五个方面的创新性研究成果:   (1)在聚集函数分类方面,依据在数据流滑动窗口环境下对聚集查询进行查询处理和查询优化所能得到的空间性能最优方法的不同提出对聚集函数进行分类的标准,这个聚集函数分类标准将成为后续工作的理论基础。   (2)在滑动窗口最值查询处理方面,给出利用空间性能最优的抽样大纲在数据流滑动窗口环境下求解最值查询的方法、多个滑动窗口共享同一个抽样大纲的方法以及对抽样大纲的空间性能进行分析和估计的方法。   (3)在滑动窗口skyline查询优化方面,给出对skyline查询的结果集进行大小估计的方法、利用skyline大纲实现最优存储管理的方法以及对空间性能最优的skyline大纲的空间性能进行分析和估计的方法。   (4)在滑动窗口skyband查询优化方面,给出对skyband查询的结果集进行大小估计的方法、利用skyband大纲实现最优存储管理的方法以及对空间性能最优的skyband大纲的空间性能进行分析和估计的方法。   (5)在滑动窗口集合势查询处理方面,给出利用计数Bloom Filter近似求解滑动窗口集合势查询的三个算法并对算法的性能进行详尽的分析和比较。   本文还对给出的在数据流滑动窗口环境下对聚集查询进行查询处理和查询优化的方法进行了详详尽的理论分析,并通过实验验证了理论分析的正确性和我们给出的对滑动窗口聚集查询进行查询处理和查询优化的方法的优越性。
其他文献
组合公钥系统是一种基于标识的公钥管理方案。组合公钥系统通过公私钥因子的组合生成新的公私钥对,可以对大规模密钥进行集中的生产和管理,具有效率和实施上的优越特性。本文针
由于通过网络召开视频会议在成本和效率上的优势,视频会议系统在商业银行等大型企业获得了迅速的推广和应用。视频会议的音视频录像和相关资料是企业的重要信息资源。高效的
无线射频识别(Radio Frequency Identification)技术和下一代互联网协议IPv6技术的出现使得人们朝思暮想构建一个在任何时间,任何地点都能获取任何物品信息的“物联网(Internet o
流畅而全面的沟通一直是人类的梦想,语言不通是实现这个梦想面临的最大难题,机器翻译应运而生。自从二十世纪四、五十年代起,至今日,机器翻译的研究已经经历过近六十年的时间。从
由于液滴蒸发的换热效率远比空气流动的换热效率高,而换热问题广泛存在于微电子学等工业和民用领域。所以对液滴蒸发的研究具有重要的应用价值。空间液滴蒸发热毛细对流实验
随着软件产品规模的扩大和应用领域的扩展,对软件过程管理的要求也越来越高。在软件开发过程中,人力资源是最重要的一种资源,人力资源调度的优劣将直接影响软件开发过程的产品质
多年以来,人们一直为有效解决计算中的难解问题而苦苦求索。目前的经典计算机面对许多问题显得渺小而无助,因此人们寻找新的计算模型和新的高效计算机的努力显得恢弘而伟大。
无线信号调制方式识别是非合作通信中一个非常重要的课题,广泛应用于频谱管理、电子战等非合作接收以及认知无线电、自适应通信等非合作通信场景。目前应用最广泛的调制识别方
自从计算机用于辅助设计和制造以来,曲面编辑就一直是人们研究的热点问题。特别是近二十年来,随着计算机软硬件技术的飞速发展,计算机图形学、虚拟现实、虚拟仿真、可视化、人机
近年来,随着全球经济和信息技术的不断发展,安全问题日益突出,越来越多的领域需要可靠的身份识别。生物特征识别技术为此提供了一种解决方案,而指纹识别技术是其中的最佳选择之一
学位