论文部分内容阅读
随着计算机技术的不断发展,现实生活开始频繁出现类似于无线射频识别(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进行实验比对分析,实验结果表明,本文提出的索引结构和算法具有良好的性能优势。