基于网格索引结构的TNN查询算法

Transitive Nearest Neighbors Queries Algorithm Based on Grid Index Structure

目的应用网格索引结构实现TNN查询算法,提高查询效率.方法将首次查询到的TNN路径长设为探测距离,利用它缩小有效查询区域,随着查询的进行,不断更新探测距离,直至终止条件到达查询结束.结果实验表明,在同等条件下,利用网格索引比利用R-tree索引结构进行查询的效率至少高一倍,而且随着目标点个数的增加,优势更加明显.结论运用网格索引并选择合适的网格粒度实现TNN查询优于运用R-tree索引实现的算法.

We used grids to index points in order to achieve TNN queries, which took shorter runtime than using R- tree. We executed query one time at the beginning, then set the sum of TNN distance to be probe distance, which pruned the search space effectively. Continming the queries, the probe distance may shrink. Queries wouldn＇t stop until the termination condition arrived. Based on the real- life datasets, we compared and analyzed the experiments＇ results, which showed that under the same conditions, our method was much more efficient than R - tree indices. And when the suitable grids granularity is set, the advantage is more and more obvious with the numbers of the object points increasing.