TY - JOUR
T1 - Efficient processing of reverse nearest neighborhood queries in spatial databases
AU - Islam, Md Saiful
AU - Shen, Bojie
AU - Wang, Can
AU - Taniar, David
AU - Wang, Junhu
N1 - Funding Information:
This work is partially supported by a Griffith University’s 2018 New Researcher Grant Australia with Dr. Md. Saiful Islam being the Chief Investigator. We appreciate the anonymous reviewers for their insightful feedback to improve the presentation quality of the paper.
Publisher Copyright:
© 2020 Elsevier Ltd
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/9
Y1 - 2020/9
N2 - This paper presents a novel query for spatial databases, called reverse nearest neighborhood (RNH) query, to discover the neighborhoods that find a query facility as their nearest facility among other facilities in the dataset. Unlike a reverse nearest neighbor (RNN) query, an RNH query emphasizes on group of users instead of an individual user. More specifically, given a set of user locations U, a set of facility locations F, a query location q, a distance parameter ρ and a positive integer k, an RNH query returns all ρ-radius circles C enclosing at least k users u∈U, called neighborhoods (NH) such that the distance between q and C is less than the distance between C and any other facility f∈F. The RNH queries might have many practical applications including on demand facility placement and smart urban planning. We present an efficient approach for processing RNH queries on location data using R-tree based data indexing. In our approach, first we retrieve candidate RNH users by an efficient bound, prune and refine technique. Then, we incrementally discover RNHs of a query facility from these candidate RNH users. We also present the variants of RNH queries in spatial databases and propose solutions for them. We validate our approach by conducting extensive experiments with real datasets.
AB - This paper presents a novel query for spatial databases, called reverse nearest neighborhood (RNH) query, to discover the neighborhoods that find a query facility as their nearest facility among other facilities in the dataset. Unlike a reverse nearest neighbor (RNN) query, an RNH query emphasizes on group of users instead of an individual user. More specifically, given a set of user locations U, a set of facility locations F, a query location q, a distance parameter ρ and a positive integer k, an RNH query returns all ρ-radius circles C enclosing at least k users u∈U, called neighborhoods (NH) such that the distance between q and C is less than the distance between C and any other facility f∈F. The RNH queries might have many practical applications including on demand facility placement and smart urban planning. We present an efficient approach for processing RNH queries on location data using R-tree based data indexing. In our approach, first we retrieve candidate RNH users by an efficient bound, prune and refine technique. Then, we incrementally discover RNHs of a query facility from these candidate RNH users. We also present the variants of RNH queries in spatial databases and propose solutions for them. We validate our approach by conducting extensive experiments with real datasets.
KW - Influence zone
KW - Nearest enclosing circle
KW - Queries and algorithms
KW - Reverse nearest neighborhood
UR - http://www.scopus.com/inward/record.url?scp=85083331029&partnerID=8YFLogxK
U2 - 10.1016/j.is.2020.101530
DO - 10.1016/j.is.2020.101530
M3 - Article
AN - SCOPUS:85083331029
SN - 0306-4379
VL - 92
JO - Information Systems
JF - Information Systems
M1 - 101530
ER -