不确定数据索引及其范围查询处理技术研究

摘要

近些年来，随着数据采集技术的日益丰富和迅猛发展，人们可以利用的数据资源急剧增加，对海量数据进行科学组织、存储和管理的数据库技术得到了广泛的应用。另外，随着人们对客观世界认识的逐步深入，现实应用中普遍存在的数据不确定性开始得到业界的重视。在不确定数据库中加入索引可以极大的提高数据的查询效率，因此，如何引入有效的索引机制来管理不确定数据并且高效的支持查询操作成了数据库领域的研究热点。
　　虽然在传统数据库领域中范围查询得到了系统的研究，但是由于不确定数据一般都带有概率，传统的范围查询算法都不能直接应用于不确定数据库。为了解决这个问题，本文提出了两种不同的索引算法，可以有效的支持基于不确定数据的概率阈值查询。本文的主要工作概括如下:
　　(1)定义了边界概率的概念并提出了一种基于边界概率的索引算法。利用在结点中附加的边界概率信息，设计了一组快速计算查询区域与不确定区域相交部分的概率上界和下界的算法，通过对不确定对象进行过滤，避免了直接计算出现概率。该索引算法是完全动态的，可以实现不确定对象的任意插入和删除，而且对不确定对象所服从的概率密度函数的类型没有限制。实验结果表明，该索引算法是一种高效的索引算法，在系统I/O、CPU时间等性能上优于其他不确定数据索引算法。
　　(2)给出了划分的规则并提出了一种基于划分的索引算法。该算法的基本思想是首先将不确定对象的不确定区域划分成若干元组，接着将MBR接近的元组重新合并成新的单元，最后利用规则过滤，从而减少了落入候选集中的不确定对象，提高了查询效率。该索引算法可以对服从任意概率密度函数的不确定对象进行查询，而且对于查询区域的大小和形状是不敏感的。实验结果表明，较之其他不确定数据索引算法，该索引算法具有更好的查询处理性能。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 不确定数据

1．2．1 产生原因

1．2．2 表现形式

1．2．3 应用场景

1．3 范围查询

1．4 问题的提出及意义

1．5 论文组织结构

第2章 相关研究工作

2．1 多维索引

2．2 概率阈值查询

2．3 确定数据索引算法

2．3．1 R-tree

2．3．2 R*-tree

2．4 不确定数据索引算法

2．4．1 PTI

2．4．2 U-tree

2．5 本章小结

第3章 基于边界概率的索引算法

3．1 研究动机

3．2 问题描述

3．2．1 查询流程

3．2．2 蒙特卡洛方法

3．3 基于边界概率的索引算法

3．3．1 边界概率

3．3．2 索引结点设计

3．3．3 过滤规则

3．4 索引结构的主要操作

3．4．1 查询操作

3．4．2 插入操作

3．4．3 删除操作

3．5 实验与性能分析

3．5．1 实验环境

3．5．2 实验数据集

3．5．3 实验方案

3．5．4 实验结果

3．6 本章小结

第4章 基于划分的索引算法

4．1 研究动机

4．2 问题描述

4．2．1 符号定义

4．2．2 倒排索引

4．3 划分规则

4．4 主要操作的算法描述

4．4．1 查询算法

4．4．2 插入算法

4．4．3 删除算法

4．5 实验与性能分析

4．5．1 实验环境

4．5．2 实验数据集

4．5．3 实验方案

4．5．4 实验结果

4．6 本章小结

第5章 总结与展望

5．1 内容总结

5．2 未来展望

参考文献

致谢

攻读硕士期间参加的项目和发表的论文