On Efficient Obstructed Reverse Nearest Neighbor Query Processing

Publication Type

Conference Proceeding Article

Publication Date

11-2011

Abstract

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.

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS'11): November 1-4, 2011, Chicago, Illinois

First Page

191

Last Page

200

ISBN

9781450310314

Identifier

10.1145/2093973.2094000

Publisher

ACM

City or Country

Chicago, IL

Additional URL

http://dx.doi.org/10.1145/2093973.2094000

Link to Full Text

Share

COinS