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

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

传统的路网上的反最远邻查询是直接找出查询点的反最远邻,这种方法不但效率不高,而且需要大量内存资源进行预计算。为了更有效地解决基于路网的单色和双色反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.