轮廓聚合查询算法的研究

论文摘要

轮廓查询在涉及多标准决策的空间数据库、数据挖掘、测试观察、用户偏好查询、可视化等领域起着非常重要的作用,是一种典型的复杂查询。目前的研究主要涉及简单的轮廓查询,而不能满足实际应用的需求,基于此,本文提出了轮廓聚合查询,以满足复杂查询应用需求,并提出相应的查询处理方法。本文通过对不同聚合函数的分析,提出了在一般聚合情况下的基本算法——聚合优先算法AACN(Aggregate All,Compute Next).AACN算法的基本思想就是先对数据集按着数据点进行聚合操作,然后再对得到的数据列表进行轮廓查询。在此基础上对算法进行了分析与改进,提出了在特殊聚合函数下的时刻优先算法CETAN(Compute on Every Time,Aggregate Next)和基于过滤策略的动态优化ABT(Aggregation Based onTime)算法.其中CETAN算法就是先对每一个时刻的数据进行轮廓查询,再对得到的结果进行聚合操作；ABT算法的基本思想就是采用过滤策略不断地对数据集进行过滤更新,最终得到想要的结果,这种算法支持数据集动态的更新。最后通过实验,模拟出3种数据集：正相关数据集、反相关数据集、不相关数据集,来分别对算法进行测试。实验结果表明了算法是有效的,对于历史数据的查询,算法可以极大地改善查询的精确性和多样性。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 研究背景
• 1.2 问题的提出
• 1.3 研究意义
• 1.4 组织结构
• 第二章 相关工作
• 2.1 轮廓查询相关工作
• 2.1.1 轮廓查询操作符
• 2.1.2 块嵌套循环方法
• 2.1.3 分而自治的轮廓查询
• 2.1.4 位图轮廓查询
• 2.1.5 B-tree索引轮廓查询
• 2.1.6 R-tree索引轮廓查询
• 2.1.7 边界区域轮廓查询
• 2.1.8 基于排序过滤的轮廓查询
• 2.2 相关问题
• 2.2.1 K-NN问题
• 2.2.2 TOP-K问题
• 2.2.3 Convex Hull问题
• 2.3 轮廓查询最新研究
• 2.3.1 基于流上的轮廓查询
• 2.3.2 基于时间序列的多维轮廓查询
• 2.3.3 在多维空间上的K-dominant轮廓查询
• 2.3.4 分布式环境下的轮廓问题
• 2.4 本章小结
• 第三章 轮廓聚合查询问题
• 3.1 基本概念
• 3.1.1 轮廓查询相关定义
• 3.1.2 轮廓查询相关性质
• 3.2 轮廓聚合查询
• 3.3 本章小结
• 第四章 轮廓聚合查询基本算法
• 4.1 相关定理
• 4.2 基本算法描述
• 4.2.1 聚合操作模块
• 4.2.2 轮廓查询模块
• 4.3 算法分析
• 4.4 本章小结
• 第五章 轮廓聚合查询的改进算法
• 5.1 轮廓优先算法
• 5.1.1 框架介绍
• 5.2 基于过滤策略的动态优化算法
• 5.2.1 聚合过滤模块算法
• 5.2.2 轮廓查询模块
• 5.3 算法分析
• 5.4 本章小结
• 第六章 实验测试与分析
• 6.1 测试维度对算法效率的影响
• 6.2 测试时刻个数对算法效率的影响
• 6.3 测试数据集大小对算法效率的影响
• 6.4 本章小结
• 第七章 结束语
• 7.1 本文总结
• 7.2 工作展望
• 参考文献
• 致谢
• 攻硕期间参与的项目及发表的论文