基于VAR树的反向最近邻查询技术的研究

Research of Reverse Nearest Neighbor Query Technology Based on VAR-Tree

在空间数据库中,反向最近邻查询技术是最重要的查询技术之一,它是在最近邻查询技术的基础上提出的,如何有效地实现反向最近邻查询一直是人们研究的热点。以往都是基于类似R树索引结构的查询,在高维的情况下,使查询的速度急剧下降,形成"维数灾难"。因此引用了一种新的索引结构——VAR树,并对VAR树进行了改进,引进了性能优越的SR树,并给出了基于这种索引结构的最近邻和反最近邻查询的算法。经实验验证基于VAR树的反向最近邻查询算法,在高维空间中的查询效率有了较大的提高。

In the spatial database,the reverse nearest neighbor query is one of the most important queries,which is based on the nearest neighbor query,how to implement effectively the reverse nearest neighbor queries have been a hot issue.In the past,most are based on R-tree index structure similar to the query,in the case of high-dimensional,making the sharp decline in the rate of inquiries,a＂dimension disaster＂.Propose a new index structure-VAR tree and introduce the SR tree of high performance after improving the VAR-tree,and give nearest neighbor queries and anti-nearest neighbor algorithms based on the structure.Experiments show that the algorithm of the reverse nearest neighbor queries based on VAR-tree enhances the query efficiency in high-dimensional space.