路网上的单色和双色反k最远邻查询  

Efficient algorithm for monochromatic and bichromatic reverse k furthest neighbor in road networks

作　　者：王宝文[1,2] 彭川[1,2] 陈子军[1,2] 刘文远[1,2] 

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004 [2]河北省计算机虚拟技术与系统集成重点实验室,河北秦皇岛066004

出　　处：《计算机工程与设计》2012年第8期3099-3104,共6页Computer Engineering and Design

摘　　要：传统的路网上的反最远邻查询是直接找出查询点的反最远邻,这种方法不但效率不高,而且需要大量内存资源进行预计算。为了更有效地解决基于路网的单色和双色反k最远邻查询问题,提高反k最远邻查询的效率,提出了从反最近邻的角度来分析反最远邻查询问题,把反最远邻查询转化为反最近邻问题。根据这一理论,提出了一种有效的基于路网的单色和双色的反k最远邻查询算法。通过实验与实验分析表明,该方法具有良好的实用价值。The traditional reverse furthest neighbor query in road networks is to directly search the reverse furthest neighbor of query point. The efficiency of this algorithm is not high, and need a lot of memory resource to preprocess. To effectively solve the problem of monochromatic and bichromatic reverse k furthest neighbor query in road networks and improve the efficiency of reverse k furthest neighbor query, a new solution is proposed, which is from the angle of reverse nearest neighbor query to analysis reverse furthest neighbor query, and translates reverse furthest neighbor query into reverse nearest neighbor query. Acco~ ding to this theory, an effective algorithm of monochromatic and bichromatic reverse k furthest neighbor query in road networks is put forward. Results and analyses of experiment show that this method has better practical value.

关 键 词：反最远邻 最远邻 单色查询 双色查询 路网 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]