Generalized Vicinity Query Algorithm in Road Network Distance

Abstract

Vicinity queries include set k nearest neighbor (SetkNN) query, ordered k nearest neighbor (OrderkNN) query, bi-chromatic reverse nearest neighbor (BRkNN) query and distance range query. In existing approaches, each type of queries has been individually studied because they are different in query criteria. Moreover, these types of queries take long processing time in calculating road network distances. To improve in the efficiency, this paper proposes vicinity query algorithm based on the higher-order network Voronoi region (NVR) which gives a unified procedure to run these different queries in an integrated framework although the query criteria of all individuals differ from each query type. Through extensive experiments, the proposed method significantly outperforms the existing works in terms of processing time by nearly two orders of magnitude.