On efficient obstructed reverse nearest neighbor query processing

• DOI: 10.1145/2093973.2094000
• Publication Date: 2012-01-17T17:20:41Z
• Authors: Yunjun Gao; Jiacheng Yang; Gang Chen; Baihua Zheng; Chun Chen
• Keywords: Heuristics; Pruning; Fixed-radius near neighbors; Nearest-neighbor chain algorithm; Best bin first; Nearest neighbor graph

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