基于不确定数据的范围查询算法的研究与实现

摘要

随着计算机技术的不断发展，现实生活开始频繁出现类似于无线射频识别(RFID)，GPS导向，无线传感器，雷达测速等实际应用。由于信息采集技术，信息存储等客观因素的限制以及仪器设备精密度的限制，导致了不确定数据的产生。不确定数据固有的不确定性使得在管理不确定数据时引入了概率的需求，概率可以较准确的描述不确定数据的属性相关值。所以，尽管传统的数据库管理技术已达到比较成熟的阶段，但由于没有考虑概率需求，传统的数据管理技术已不再适用于不确定数据，这对数据库理论与技术提出了新的挑战。目前，虽然不确定数据通常都采用概率数据模型表示，较强的表示了不确定数据间的相关性，但在查询与概率推理方面其时间复杂度相对过高。所以，研究一个能支持不确定数据的高效索引和快速查询算法是当前的重点也是热点问题。
　　本文针对不确定数据查询问题，进行了一定的分析与研究。首先，提出了一种新的索引结构S-Box来管理不确定数据。这种结构可以有效地支持基于概率数据的范围查询。S-Box是一种由R-tree改进而来的树型结构。在索引结构中，主要记录本论文提出的一种新的框架——skeleton。在S-Box的每个节点中，都记录了一组skeleton，它可以在空间上为查询提供一个非常紧凑的边界约束bound，以至于可以过滤掉与查询区域没有重叠的部分对象，减少查询的访问代价和时间开销，提高查询速度。
　　其次，提出一种新的数据结构BBD+-tree管理不确定数据对象。BBD+-tree采用多分辨率网格很好的刻化了对象的概率密度函数，在概率上为查询提供了紧凑的bound。
　　再者，基于S-Box的索引结构，提出了两种查询算法对不确定数据进行范围查询。算法SBO利用S-Box返回出现在一个查询区域内的概率大于某一概率阈值的不确定数据对象。算法中用到了骨架skeleton和剪枝策略，使得查询可以大范围的减小搜索空间和计算开销，从而提高查询速度和效率。进一步，提出了SBO算法的优化算法SCFB，算法的基本思想与SBO基本一样，不同的是文章设计了一个过滤器CF，这个过滤器CF用在访问对象对应的BBD+-tree之前。如果对象可以通过CF直接被剪枝掉，则就不需要访问BBD+-tree，减少了访问BBD+-trree的时间开销，否则，需要继续访问BBD+-tree。SCFB算法进一步在时间开销上进行了优化，使得查询更加快速有效。
　　最后，为了分析验证S-Box结构以及相关算法的性能优势，本文做了大量的比对试验。通过与典型的U-Tree，UD-Tree进行实验比对分析，实验结果表明，本文提出的索引结构和算法具有良好的性能优势。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 研究目的和意义

1．3 本文研究的主要内容

1．4 本文的组织结构

第二章 相关工作

2．1 不确定数据

2．1．1 不确定数据的产生

2．1．1 不确定数据的定义

2．2 不确定数据相关研究

2．3 不确定数据范围查询

2．4 不确定数据的索引技术

2．4 本章小结

第三章 基于不确定数据的S-Box索引

3．1 S-Box索引的框架

3．2 S-Node的结构及访问算法

3．2．1 S-Node的数据结构

3．2．2 skeleton的定义和初始化

3．2．3 S-Node的访问算法

3．3 BBD+-tree的结构和遍历算法

3．3．1 构造BBD+-tree

3．3．2 BBD+-tree的数据结构

3．3．3 BBD+-tree的节点类型

3．3．4 BBD+-tree的遍历

3．4 S-Box的更新算法

3．4．1 插入算法

3．4．2 删除算法

3．5 本章小结

第四章 S-Box的查询算法与代价分析

4．1 S-Box的查询算法

4．1．1 SBO算法

4．1．2 SBO算法的优化算法SCFB

4．2 S-Box算法的复杂度分析

4．2．1 S-Node的复杂度分析

4．2．2 BBD+-tree的复杂度分析

4．2．3 算法复杂度的比较分析

4．3 本章小结

第五章 实验测试及结果分析

5．1 实验环境及数据集信息

5．2 索引效率评估

5．3 查询性能评估

5．4 本章小结

第六章 工作总结和展望

6．1 工作总结

6．2 工作展望

参考文献

致谢