Maximizing bichromatic reverse nearest neighbor for Lp-norm in two- and three-dimensional spaces |
| |
| Authors: | Raymond Chi-Wing Wong M. Tamer Özsu Ada Wai-Chee Fu Philip S. Yu Lian Liu Yubao Liu |
| |
| Affiliation: | (1) The Hong Kong University of Science and Technology, Hong Kong, People’s Republic of China;(2) University of Waterloo, Waterloo, Canada;(3) The Chinese University of Hong Kong, Hong Kong, People’s Republic of China;(4) University of Illinois at Chicago, Chicago, USA;(5) Sun Yat-Sen University, Guangzhou, People’s Republic of China |
| |
| Abstract: | Bichromatic reverse nearest neighbor (BRNN) has been extensively studied in spatial database literature. In this paper, we study a related problem called MaxBRNN: find an optimal region that maximizes the size of BRNNs for L p -norm in two- and three- dimensional spaces. Such a problem has many real-life applications, including the problem of finding a new server point that attracts as many customers as possible by proximity. A straightforward approach is to determine the BRNNs for all possible points that are not feasible since there are a large (or infinite) number of possible points. To the best of our knowledge, there are no existing algorithms which solve MaxBRNN for any L p -norm space of two- and three-dimensionality. Based on some interesting properties of the problem, we come up with an efficient algorithm called MaxOverlap for to solve this problem. Extensive experiments are conducted to show that our algorithm is efficient. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
