道路网络中k路径最近邻居针对两种目标点的应用  

An Application of k Path Nearest Neighbor with Two Types of Data Objects in Road Networks

作　　者：宋海涛[1] 张守志[1] 施伯乐[1] 

机构地区：[1]复旦大学计算机科学技术学院,上海201203

出　　处：《小型微型计算机系统》2012年第8期1761-1764,共4页Journal of Chinese Computer Systems

摘　　要：提出一种道路网络中针对两种不同类型目标点的k组路径最近邻居查询,这是一种新的查询:给出用户希望到达的终点位置以及两组目标点集合,这种查询返回连接用户当前位置和终点位置的最短路径,以及相对于这条最短路径的k组路径最近邻居,每组包含两个不同类型的目标点,将这种查询命名为k-PNNT.提出了一种典型的过滤-精炼算法得到k-PNNT及对应的最短路径,并且在实际道路网络中进行了实验.实验证明,算法可行,有效.A query to k path nearest neighbor with two types of data objects in road networks is proposed, it is a new type of query： given a destination where a user is going to and two sets of data objects, this query returns the shortest path connecting the destination and the user＇s current location, and the k-PNN with two types of data objects, We name this query k-PNNT. We propose a filter-refine algorithm to get k-PNNT and the corresponding shortest path, and conduct extensive experiment on real road networks. The algorithm is proved to be efficient according to the experimentation.

关 键 词：k路径最近邻居 两类目标点 道路网络 过滤精炼 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]