论文部分内容阅读
近年来,随着无线通信和全球定位系统(Global Positioning System, GPS)定位技术的发展,移动环境下的查询技术研究已经成为移动数据库领域的热点。而其中的移动对象K近邻查询更是查询技术中的重要研究对象之一。K近邻查询的研究已经有很多成果,像基于Bx树、Bdual树、TPR树的查询等,而其中比较高效的是将voronoi图运用到K近邻的查询,利用voronoi图的特性,提高了查询的效率。但该索引在移动对象数据量和网格划分个数的比值较小时性能较差。因此,本文以该问题作为切入点,进行了深入的研究。首先,Del-VGQ索引由Delaunay三角网和虚拟网格四分树(Virtual Grid Quadtree, VGQ)构成。它具备了VGQ索引的快速定位特点和Delaunay三角网能表达对象的邻近性质,适合做K近邻查询,但是该索引在Delaunay三角网结点的插入删除时会递归检查周围的三角形是否满足空圆特性,性能较差。因此本文针对Delaunay三角网的这个特点,运用延时删除策略,对Del-VGQ索引进行扩展,提出了K近邻查询算法OptDelVGQKnnQuery并证明了该算法的正确性。接着本文对索引的性能进行了仿真实验。实验结果表明在移动对象数据量和网格个数的比值较小时,新索引的吞吐量是旧索引的三倍。其次,Del-VGQ索引中运用到了四分树,而四分树并不具有平衡的特性,在数据分布不均匀时,性能下降很大。针对这个特点,本文用具有平衡特性的R树代替四分树,提出了DelRtreeKnnQuery算法,接着本文对索引性能进行了仿真实验。实验结果表明在移动对象数据量和网格个数的比值较小时,新索引的吞吐量是旧索引的两倍。最后,Del-VGQ索引中网格划分是固定划分,这使得数据分布不均匀时,不同网格移动对象数量相差巨大,严重影响了索引更新和查询的效率。针对这个特点,本文设计了均匀密度模型,此时网格划分不固定,只有当网格内移动对象个数超过某个阈值才会划分,尽量使每个网格内的移动对象数量相同,提高了索引更新和查询的效率。在此基础上本文提出了DelVGQAVGKnnQuery算法,并对该索引的性能进行了仿真实验。实验结果表明在移动对象数据量和网格个数比值较小时,新索引吞吐量是旧索引的十倍。