Continuous maximal reverse nearest neighbor query on spatial networks

Abstract

Given a set S of sites and a set O of weighted objects located on a road network, the optimal network location (ONL) query computes a location on the road network where introducing a new site would maximize the total weight of the objects that are closer to the new site than to any other site. The existing solutions for optimal network location query assume that sites and objects rarely change their location over time, whereas there are numerous new applications with which sites and/or objects frequently change location. Unfortunately, the existing solutions for optimal network location query are not applicable to answer such these so-called dynamic optimal network location queries (DONL), since the result generated by such solutions is most probably invalid by the time computation is complete. In this paper for the first time we formalize the problem of DONL queries as Continuous Maximal Reverse Nearest Neighbor (CMaxRNN) queries on spatial networks, and introduce an approach that allows for efficient and incremental update of MaxRNN query results on spatial networks. With an extensive experimental study we verify and evaluate the efficiency of our proposed approach with both synthetic and real-world datasets.