Abstract: 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 RANK is reached through the algorithms of ANN query and Division ctuery with primary candidates. The experimental results indicate that the Rav-tree is an effective index structure and has better efficiency and recall for the query such as RANN query.

Key words: Index structure, Reverse approximate nearest neighbor, Division cauery, Region estimation