Reverse k-nearest neighbour schedules in time-dependent road networks
Felix Borutta, Mário A. Nascimento, Johannes Niedermayer, Peer Kröger · 2015
Despite the wealth of research published on reverse k-nearest neighbour (RkNN) queries very few attempts have been made to solve the problem in time-dependent networks, i.e., networks where the edge cost varies with time. A typical example of such network is one made of a city's streets. An interesting consequence of such assumption is that set of RkNNs can change over time even if the objects are not moving. We present an efficient algorithm that computes a RkNN schedule for a given time interval, e.g., one day. Once computed, such schedule allows one to find the RkNNs for any point within the given time interval doing a simple table lookup. We experimentally evaluate our novel methods using a straightforward solution, namely computing the RkNN set for every (discrete) instant within a time interval. Our results show that the proposed algorithms are orders of magnitude faster than such baseline approach.