Reverse k nearest neighbors queries and spatial reverse top-k queries

Publication Type:
Journal Article
VLDB Journal, 2017, 26 (2), pp. 151 - 176
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Reverse k nearest neighbors queries and spatial reverse top-k queries.pdfPublished Version2.41 MB
Adobe PDF
© 2016, Springer-Verlag Berlin Heidelberg. Given a set of facilities and a set of users, a reverse k nearest neighbors (RkNN) query q returns every user for which the query facility is one of the k closest facilities. Almost all of the existing techniques to answer RkNN queries adopt a pruning-and-verification framework. Regions-based pruning and half-space pruning are the two most notable pruning strategies. The half-space-based approach prunes a larger area and is generally believed to be superior. Influenced by this perception, almost all existing RkNN algorithms utilize and improve the half-space pruning strategy. We observe the weaknesses and strengths of both strategies and discover that the regions-based pruning has certain strengths that have not been exploited in the past. Motivated by this, we present a new regions-based pruning algorithm called Slice that utilizes the strength of regions-based pruning and overcomes its limitations. We also study spatial reverse top-k (SRTk) queries that return every user u for which the query facility is one of the top-k facilities according to a given linear scoring function. We first extend half-space-based pruning to answer SRTk queries. Then, we propose a novel regions-based pruning algorithm following Slice framework to solve the problem. Our extensive experimental study on synthetic and real data sets demonstrates that Slice is significantly more efficient than all existing RkNN and SRTk algorithms.
Please use this identifier to cite or link to this item: