EINN最近邻居查询索引遍历算法改进

Improvement of the EINN Algorithm for NN Query Traversing

最近邻居查询是时空数据库的关键技术。目前,基于R TREE系列索引结构的EINN最近邻居查询遍历算法具有访问最少数据块找到最近邻居的优势,但存在时空运算冗余的不足。鉴于此,通过一定的内存资源代价,减少最近邻居查询索引遍历过程中的时空运算次数,对算法EINN进行改进。实验证明,在保证数据块访问数量不变的情况下,改进算法S EINN在时空运算开销方面比算法EINN有较大优势。

NN Query is a key technology in spatio-temporal databases. Recently, the EINN algorithm, which is an algorithm for NN Query traversing based on the R-TREE family,has the advantage of finding the nearest neighbour by accessing the least data pages, but it has the disadvantage of spatio-temporal computing redundance. So, this paper proposes an improved algorithm S-EINN, which cuts down the times of spatio-temporal computation. Experimental results show that S-EINN has more advantage than EINN in spatio-temporal computing.