Paper Info
Title
Finding optimal region for bichromatic reverse nearest neighbor in two- and three-dimensional spaces
Abstract
The MaxBRNN problem is to find an optimal region such that setting up a new service within this region might attract the maximum number of customers by proximity. The MaxBRNN problem has many practical applications such as service location planning and emergency schedule. In typical real-life applications the data volume of the problem is huge, thus an efficient solution is highly desired. In this paper, we propose two efficient algorithms, namely, OptRegion, and 3D-OptRegion to tackle the MaxBRNN problem and MaxBRkNN in two- and three-dimensional spaces, especially for the 3D-OptRegion, we propose a powerful pruning strategy Fine-grained Pruning Strategy to reduce the searching space. Our method employs three optimization techniques, i.e., sweep line (sweep plane in a three-dimensional space), pruning strategy (based on upper bound estimation), and influence value computation (of candidate points), to improve the search performance. In a three-dimensional space, we additionally use a fine-grained pruning strategy to further improve the pruning effect. Extensive experimental evaluation using both real and synthetic datasets confirms that both OptRegion and 3D-OptRegion outperform the existing algorithms significantly under all problem instances.
Year
DOI
Venue
2016
10.1007/s10707-015-0239-5
GeoInformatica
Keywords
Field
DocType
Spatial databases,Reverse nearest neighbor query,Three dimensional space
k-nearest neighbors algorithm,Three-dimensional space,Data mining,Mathematical optimization,Upper and lower bounds,Mathematics,Sweep line algorithm,Service location,Pruning,Computation
Journal
Volume
Issue
ISSN
20
3
1384-6175
Citations 
PageRank 
References 
2
0.37
24
Authors
4
Name
Order
Citations
PageRank
Huaizhong Lin16712.34
Fangshu Chen2122.20
Yunjun Gao386289.71
Dongming Lu416332.29