Rav-tree:一种有效支持反向近似近邻查询的索引结构

Rav-tree:An Efficient Index Structure for Reverse Approximate Nearest Neighbor Query

空间数据库的索引结构是实现有效数据查询的前提和基础。空间数据反向近似近邻查询是空间查询的一个新方向,它避免了精确查询中过多的距离计算,从而能够在效率与准确性上取得平衡。提出的Rav-tree不同于基于启发式规则的索引结构,首先利用局部近似,然后根据Voronoi cell区域和估计圆的方法实现近似近邻查询,并利用过滤结果和分域查询得到初步的候选集,最终通过反向近似近邻查询(RANNQuery)算法得到RANN集,并完整地给出基于Rav-tree的ANN查询算法和RANN查询算法。实验结果表明,Rav-tree对RANN等查询具有较好的查询效率和查全率。

Index structure is the precondition and foundation in the efficient data query. The reverse approximate nearest neighbor query is a new issue in the area of spatial query. This approach can avoid much metric distance computation in exact query,and acquire a better tradeoff between the efficiency and precision. The Rav-tree is different from the index structures based on the heuristic rules. It applies partial Voronoi cell approximation with estimated circles to filter the results of approximate nearest neighbor query. The final result set of RANN is reached through the algorithms of ANN query and Division query with primary candidates. The experimental results indicate that the Ray-tree is an effective index structure and has better efficiency and recall for the query such as RANN query.