【作者】 殷晓岚； 丁治明； 李京；

【Author】 Yin Xiaolan~(1,3),Ding Zhiming~2,and Li Jing~1 1(Technology Center of Software Engineering,Institute of Software,Chinese Academy of Sciences,Beijing 100080) 2(Technology Center of Basic Software,Institute of Software,Chinese Academy of Sciences,Beijing 100080) 3(Graduate University of Chinese Academy of Sciences,Beijing 100049)

【机构】 中国科学院软件研究所软件工程技术研发中心； 中国科学院研究生院； 中国科学院软件研究所基础软件工程中心；

【摘要】 在空间网络数据库中,基于位置的服务是一项重要功能,而k-NN查询是实现该服务的重要查询.在网络上有一个原始对象(例如在道路上行驶的汽车),有一组目标对象(例如旅店、加油站、救护车等等),k-NN查询返回距离原始对象最近的k个目标对象.在这种对象移动受到网络限制的情况下,网络距离将替代Euclidean距离作为k-NN查询的指标.提出了一种解决移动对象k-NN查询的算法,该算法使用了一组索引结构来解决移动对象的位置问题.实验分析表明这种方法比传统方法的执行效率更高.更多还原

【Abstract】 One of the most important kinds of queries in spatial network databases(SNDB) to support location-based services(LBS) is the k-nearest neighbors(k-NN) query.Given a object in a network,e.g. a location of a car on a road network,and a set of objects of interests,e.g.hotels,gas station,car,etc. the k-NN query returns the k objects of interest closest to the query object.The network distance,instead of the Euclidean distance,is used in such a query.Proposed in this paper is a k-NN algorithm with a set of index structures to support the situation of moving objects.Experimental evaluation with generated data sets shows that this proposal is more efficient than the traditional solution to this problem.更多还原