Reverse Approximate Nearest Neighbor Queries on Road Network
- PDF / 1,834,437 Bytes
- 18 Pages / 439.642 x 666.49 pts Page_size
- 82 Downloads / 194 Views
Reverse Approximate Nearest Neighbor Queries on Road Network Xinyu Li1 · Arif Hidayat2
· David Taniar1 · Muhammad Aamir Cheema1
Received: 19 February 2020 / Revised: 21 July 2020 / Accepted: 25 September 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Reverse k Nearest Neighbor (RkNN) queries retrieve all objects that consider the query as one of their k most influential objects. Given a set of user U , a set of facilities F and a value k, a facility f is said to be influential to a user u if f is one of the k closest facilities to u. As a complement of RkNN query, Reverse Approximate Nearest Neighbor (RANN) query considers relaxed definition of influence, where a user u is influenced by not only its closest facility, but also by every other facility that is almost as close to u as its closest facility is. In this paper, we study RANN query on road network. Existing RANN techniques and algorithms only work for queries on Euclidean space and are not directly applicable for RANN queries on road network. We propose pruning techniques that utilize Network Voronoi Diagram (NVD) to efficiently solve RANN query on road network. We conduct extensive experimental study on different real data sets and demonstrate that our algorithm is significantly better than the competitor. Keywords RkNN · RANN · NVD
1 Introduction With the increase of internet speed, more affordable geo-position locator and cheaper bandwidth cost, online map applications have become an essential part in today’s human life. Arif Hidayat
[email protected]; [email protected] Xinyu Li [email protected] David Taniar [email protected] Muhammad Aamir Cheema [email protected] 1
Faculty of Information Technology, Monash University, Melbourne, Australia
2
Brawijaya University, Malang, Indonesia
World Wide Web
Many leading and start up companies provide map or navigation service as one of their main services, such as Google, Uber, Grab etc. Online map application service allows user to submit various spatial queries, like shortest path query, nearest neighbor query, range query etc. All those online map applications use road network distance which give more accurate distance information compared to the Euclidean distance. In this paper, we study Reverse Approximate Nearest Neighbor (RANN) query. It was introduced in [11, 12] as a complement of Reverse k Nearest Neighbor (RkNN) query. Formally, given a set of users U , a set of facilities F , an integer k and a query facility q, an RkNN query returns every user u ∈ U that considers q as one of its k closest facilities. Consider the example of Figure 1 and assume k = 2, R2N N of f2 are u1 , u2 , u3 , u4 and u5 because f2 is among the 2 closest facilities for these users, i.e. R2N N (f2 ) = {u1 , u2 , u3 , u4 , u5 }. Similarly, R2N N (f1 ) = {u2 }, R2N N (f3 ) = {u1 } and R2N N (f4 ) = {u3 , u4 , u5 }. The RkNN query has many applications in decision support, location-based service, profile-based marketing etc. Consider an example of a supermarket
Data Loading...
