Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

7-2009

Abstract

In this paper, we study a novel form of continuous nearest neighbor queries in the presence of obstacles, namely continuous obstructed nearest neighbor (CONN) search. It considers the impact of obstacles on the distance between objects, which is ignored by most of spatial queries. Given a data set P, an obstacle set O, and a query line segment q in a two-dimensional space, a CONN query retrieves the nearest neighbor of each point on q according to the obstructed distance, i.e., the shortest path between them without crossing any obstacle. We formulate CONN search, analyze its unique properties, and develop algorithms for exact CONN query processing, assuming that both P and O are indexed by conventional data-partitioning indices (e.g., R-trees). Our methods tackle the CONN retrieval by performing a single query for the entire query segment, and only process the data points and obstacles relevant to the final result, via a novel concept of control points and an efficient quadratic-based split point computation algorithm. In addition, we extend our solution to handle the continuous obstructed k-nearest neighbor (COkNN) search, which finds the k (?1)nearest neighbors to every point along q based on obstructed distances. A comprehensive experimental evaluation using both real and synthetic datasets has been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms.

Keywords

continuous nearest neighbor, continuous obstructed nearest neighbor, nearest neighbor, obstacle, spatial database

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

SIGMOD '09: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data: Providence, Rhode Island, USA, June 29-July 2, 2009

First Page

577

Last Page

590

ISBN

9781605585512

Identifier

10.1145/1559845.1559906

Publisher

ACM

City or Country

New York

Additional URL

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

Download

Share

COinS