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

《基于不确定数据的范围查询算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文基于不确定数据的范围查询算法的研究与实现作者姓名：指导教师：甘果王国仁教授东北大学信息科学与工程学院申请学位级别：硕士学科类别：工学学科专业名称：计算机应用技术论文提交日期：2014年6月论文答辩日期：2014年6月学位授予日期：2014年7月答辩委员会主席：评阅人：东北大学2014年6月锱易万方数据AThesisinComputerArchitectureIIIIllllllllllllllIMIlllllIY2996031ResearchandImplementationofRangeQueryAlgorithmbasedonUncerta

2、inDataByGanGuoSupervisor：ProfessorWangGuoRenNortheasternUniversityJanuary2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。学位论文作者签名：—慷日期：2014年6月21日学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东

3、北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年口学位论文作者签名：苔勇k签字日期：2014年6月2i日导师签名：签字日期：亿＼肌毯郫^皋≥础万方数据东北大学硕士学位论文摘要基于不确定数据的范围查询算法的研究与实现摘要随着计算机技术的不断发展，现实生活开始频繁出现类似于无线射频识别(RFID)，GPS导向，无线传感器，雷达测速等实际应用。由于信息采集技术，信息存储等客观因素的限制以及仪器设备精密度的限制，导致了不确定数据的产生。不确定数据固有的不确定性使得在管理不确定数据时引入了概率的需求

4、，概率可以较准确的描述不确定数据的属性相关值。所以，尽管传统的数据库管理技术已达到比较成熟的阶段，但由于没有考虑概率需求，传统的数据管理技术己不再适用于不确定数据，这对数据库理论与技术提出了新的挑战。目前，虽然不确定数据通常都采用概率数据模型表示，较强的表示了不确定数据间的相关性，但在查询与概率推理方面其时间复杂度相对过高。所以，研究一个能支持不确定数据的高效索引和快速查询算法是当前的重点也是热点问题。本文针对不确定数据查询问题，进行了一定的分析与研究。首先，提出了一种新的索引结构S．Box来管理不确定数据。这种结构可以有效地支持基于概率数据的范围查询。S-Box是一种EhR

5、．tree改进而来的树型结构。在索引结构中，我们主要记录本论文提出的一种新的框架一一skeleton。在S．Box的每个节点中，我们都记录了一组skeleton，它可以在空间上为查询提供一个非常紧凑的边界约束bound，以至于可以过滤掉与查询区域没有重叠的部分对象，减少查询的访问代价和时间开销，提高查询速度。其次，我们提出一种薪的数据结构BBD+-tree管理不确定数据对象。BBD+．tree采用多分辨率网格很好的刻化了对象的概率密度函数，在概率上为查询提供了紧凑的bound。再者，基于S．Box的索引结构，我们提出了两种查询算法对不确定数据进行范围查询。算法SBO禾t用S．

6、Box返回出现在一个查询区域内的概率大于某一概率阈值的不确定数据对象。算法中用到了骨架skeletonj}l剪枝策略，使得查询可以大范围的减小搜索空间和计算开销，从而提高查询速度和效率。进一步，我们提出了SBO算法的优化算法SCFB，算法的基本思想与SBO基本一样，不同的是我们设计了一个过滤器CF，这个过滤器CF用在访问对象对应的BBD+-tree之前。如果对象可以通过CF直接被剪枝掉，则就不需要访I'口]BBD+．tree，减少了访i'口-jBBD+_trree的时间开II万方数据东北大学硕士学位论文摘要销，否则，需要继续访／hiBBD+-tree。SCFB算法进一步在时间

7、开销上进行了优化，使得查询更加快速有效。最后，为了分析验证S．Box结构以及相关算法的性能优势，我们做了大量的比对试验。通过与典型的U．Tree，UD．Tree进行实验比对分析，实验结果表明，本文提出的索引结构和算法具有良好的性能优势。关键词：不确定数据，多分辨率网格，骨架，范围查询III万方数据东j匕大学硕士学位论文AbstractResearchandImplementationofRangeQueryAlgorithmBasedonUncertainDataAbstractWiththeconti