We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Maximizing bichromatic reverse nearest neighbor for L-norm in two- and three-dimensional spaces.
- Authors
Wong, Raymond; Özsu, M.; Fu, Ada; Yu, Philip; Liu, Lian; Liu, Yubao
- 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-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-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.
- Subjects
DATABASE marketing; INDEXING; COMPUTER algorithms; EUCLIDEAN algorithm; GEOMETRY
- Publication
VLDB Journal International Journal on Very Large Data Bases, 2011, Vol 20, Issue 6, p893
- ISSN
1066-8888
- Publication type
Article
- DOI
10.1007/s00778-011-0230-1