一种基于区域覆盖的k近邻查询方法

摘要

本发明提供一种基于区域覆盖的k近邻查询方法，属于移动数据索引技术领域，将空间进行网格划分，数据点保存在对应的网格中，再将网格作为四分树的叶子结点存储起来，同时将网格作为一个移动对象保存在Voronoi图中，查询时首先根据对象的坐标找到其所在的网格，进而找到该网格在Voronoi图中的位置，该网格内的对象按照距离的升序组织成结果链表，同时根据Voronoi图把相邻的网格按距离的升序放入访问链表中，进行距离比较，最终找到该对象的K个最近邻。本方法综合利用Voronoi图和虚拟网格四分树的索引结构，利用哈希表快速查找定位，从而提高了查询的效率。

主权项

一种基于区域覆盖的k近邻查询方法，其特征在于：包括如下步骤：步骤1：录入人员位置信息，方法为：每一个对象向上报告自己的当前坐标，确定查询空间；步骤2：把查询空间划分为网格；首先将整个查询空间划分分成M×N个虚拟的空间网格单元，其中，M表示横着将空间分为M份，N表示竖着将空间分为N份，对于点p(x，y)所在的网格id，计算公式如下：px＝(int)x/hXpy＝(int)y/hYid＝px+py×divX+1式中，x和y表示点p的横坐标和纵坐标，hX和hY分别表示网格单元的水平宽度和垂直高度，divX表示网格文件在水平方向上的划分个数；步骤3：对移动对象进行索引；把每一个空间网格单元抽象为空间中的一个点进行索引，将对动态移动对象的管理转换为网格单元管理，即只对存在移动对象的区域进行索引，对不存在移动对象的区域不进行索引，建立索引的具体方法为：对于划分后的每一个空间网格单元，若网格内区域存在移动对象，则将该空间网格单元插入到压缩四分树中；若其内部没有移动对象，则该网格并不真实存在；与此同时，采用增量构造方法以各个网格的中心点来建立Voronoi图；步骤4：根据基于区域覆盖的虚拟网格四分树与Voronoi图相结合的索引结构，进行K近邻查询。