In this paper, we study a new form of reverse nearest neighbor (RNN) queries, i.e.,  obstructed reverse nearest neighbor  (ORNN) search. It considers the impact of obstacles on the  distance  between objects, which is ignored by the existing work on RNN retrieval. Given a data set  P , an obstacle set  O , and a query point  q  in a 2D space, an ORNN query finds all the points/objects in  P  that have  q  as their nearest neighbor, according to the  obstructed distance  metric, i.e., the length of the  shortest path  between two points without crossing any obstacle. We formalize ORNN search, develop effective  pruning heuristics  (via introducing a novel  boundary region  concept), and propose efficient algorithms for ORNN query processing, assuming that both  P  and  O  are indexed by traditional data-partitioning indexes (e.g., R-trees). Extensive experiments demonstrate the effectiveness of our developed pruning heuristics and the performance of our proposed algorithms, using both real and synthetic datasets.
['Yunjun Gao', 'Jiacheng Yang', 'Gang Chen', 'Baihua Zheng', 'Chun Chen']
On efficient obstructed reverse nearest neighbor query processing