Abstract
Reverse nearest neighbor (RNN) queries have a broad application base such as decision support, profile-based marketing, resource allocation, etc. Previous work on RNN search does not take obstacles into consideration. In the real world, however, there are many physical obstacles (e.g., buildings) and their presence may affect the visibility between objects. In this paper, we introduce a novel variant of RNN queries, namely, visible reverse nearest neighbor (VRNN) search, which considers the impact of obstacles on the visibility of objects. Given a data set P, an obstacle set O, and a query point q in a 2D space, a VRNN query retrieves the points in P that have q as their visible nearest neighbor. We propose an efficient algorithm for VRNN query processing, assuming that P and O are indexed by R-trees. Ourtechniques do not require any preprocessing and employ half-plane property and visibility checkto prune the search space. In addition, we extend our solution to several variations of VRNN queries, including: 1) visible reverse k-nearest neighbor(VRkNN) search, which finds the points in P that have q as one of their k visible nearest neighbors; 2) ?-VRkNN search, which handles VRkNN retrieval with the maximum visible distance ? constraint; and 3) constrained VRkNN (CVRkNN) search, which tackles the VRkNN query with region constraint. Extensive experiments on both real and synthetic data sets have been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings. © 2009 IEEE.
Original language | English |
---|---|
Article number | 4912197 |
Pages (from-to) | 1314-1327 |
Number of pages | 14 |
Journal | IEEE Transactions on Knowledge and Data Engineering |
Volume | 21 |
Issue number | 9 |
DOIs | |
Publication status | Published - 1 Sept 2009 |
Externally published | Yes |
Keywords
- Algorithm
- Query processing
- Reverse nearest neighbor
- Spatial database
- Visible reverse nearest neighbor
ASJC Scopus subject areas
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics