Efficient method for maximizing bichromatic reverse nearest neighbor
Top Cited Papers
- 1 August 2009
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 2 (1), 1126-1137
- https://doi.org/10.14778/1687627.1687754
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. 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, the fastest known method has exponential time complexity on the data size. Based on some interesting properties of the problem, we come up with an efficient algorithm called MaxOverlap. Extensive experiments are conducted to show that our algorithm is many times faster than the best-known technique.Keywords
This publication has 8 references indexed in Scilit:
- Efficient method for maximizing bichromatic reverse nearest neighborProceedings of the VLDB Endowment, 2009
- Capacity constrained assignment in spatial databasesPublished by Association for Computing Machinery (ACM) ,2008
- Continuous Evaluation of Monochromatic and Bichromatic Reverse Nearest NeighborsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- The Optimal-Location QueryLecture Notes in Computer Science, 2005
- Influence sets based on reverse nearest neighbor queriesPublished by Association for Computing Machinery (ACM) ,2000
- The R*-tree: an efficient and robust access method for points and rectanglesPublished by Association for Computing Machinery (ACM) ,1990
- Filtering Search: A New Approach to Query-AnsweringSIAM Journal on Computing, 1986
- New upper bounds for neighbor searchingInformation and Control, 1986