With the aim of improving query efficiency for nearest neighbor (NN) query and k nearest neighbor (kNN) query,the definitions of the orders between spatial data are given. Based on the orders, the MOIS (multi-order index structure)tree, an index structure for spatial data is proposed. In the index structure it is set that the children nodes of each middle node are arranged in some order according to their geometric locations so that the positions of data can be determined quickly when NN query and k query are processed. New prunning rules for NN query and kNN query are given. By therules a lot of computation can be reduced to achieve effective data screening and filtering when corresponding query is processed. Therefore the speed of query is increased. The algorithms for NN query and kNN query are presented. The experiments show that the query efficiencies of the new algorithms presented in this paper are greatly improved, compared with those of the current algorithms used to solve the same problems.%以提高最近邻查询和k最近邻查询效率为目标,给出了空间对象间序关系的定义,以此为基础提出了一种空间数据索引结构--MOIS(multi-order index structure)-树,规定MOIS-树中的中间节点的所有孩子节点按其几何位置满足某种序的关系,从而使得在中间节点中进行最近邻和k最近邻查询时可以进行快速定位.给出了新的最近邻和k最近邻查询剪枝规则.利用这些规则在进行相应的查询时减少了许多计算,有效地对数据进行筛选和过滤,加快了查询的速度.给出了最近邻、k最近邻查询算法.实验表明:最近邻和k最近邻查询算法与现有的同类查询算法相比查询效率有较大的提高.
展开▼
