Expanding Reverse Nearest Neighbors
- Publisher:
- Association for Computing Machinery (ACM)
- Publication Type:
- Journal Article
- Citation:
- Proceedings of the VLDB Endowment, 2023, 17, (4), pp. 630-642
- Issue Date:
- 2023-12
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
In a graph the reverse nearest neighbors RNN of vertex f refer to the set of vertices that consider f as their nearest neighbor When f represents a facility like a subway station its RNN comprises potential users who prefer the nearest facility In practice there may be underutilized facilities with small RNN sizes and relocating these facilities to expand their service can be costly or infeasible A more cost effective approach involves selectively upgrading some edges e g reducing their weights to expand the RNN sizes of underutilized facilities This motivates our research on the Expanding Reverse Nearest Neighbors ERNN problem which aims to maximize the RNN size of a target facility by upgrading a limited number of edges Solving the ERNN problem allows underutilized facilities to serve more users and alleviate the burden on other facilities Despite numerous potential applications ERNN is hard to solve It can be proven to be NP hard and APX hard and it exhibits non monotonic and non submodular properties To overcome these challenges we propose novel greedy algorithms that improve efficiency by minimizing the number of edges that need to be processed and the cost of processing each edge Experimental results demonstrate that the proposed algorithms achieve orders of magnitude speedup compared to the standard greedy algorithm while greatly expanding the RNN
Please use this identifier to cite or link to this item: