Publication Type

Journal Article

Version

submittedVersion

Publication Date

6-2011

Abstract

In this paper, we identify and solve a new type of spatial queries, called continuous visible nearest neighbor (CVNN) search. Given a data set P, an obstacle set O, and a query line segment q in a two-dimensional space, a CVNN query returns a set of $${\langle p, R\rangle}$$ tuples such that $${p \in P}$$ is the nearest neighbor to every point r along the interval $${R \subseteq q}$$ as well as pis visible to r. Note that p may be NULL, meaning that all points in P are invisible to all points in R due to the obstruction of some obstacles in O. In contrast to existing continuous nearest neighbor query, CVNN retrieval considers the impact of obstacles on visibilitybetween objects, which is ignored by most of spatial queries. We formulate the problem, analyze its unique characteristics, and develop efficient algorithms for exact CVNN query processing. Our methods (1) utilize conventional data-partitioning indices (e.g., R-trees) on both P and O, (2) tackle the CVNN search by performing a single query for the entire query line segment, and (3) only access the data points and obstacles relevant to the final query result by employing a suite of effective pruning heuristics. In addition, several interesting variations of CVNN queries have been introduced, and they can be supported by our techniques, which further demonstrates the flexibility of the proposed algorithms. A comprehensive experimental evaluation using both real and synthetic data sets has been conducted to verify the effectiveness of our proposed pruning heuristics and the performance of our proposed algorithms.

Keywords

Query processing, Nearest neighbor, Visible, Spatial database, Algorithm

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

VLDB Journal

Volume

20

Issue

3

First Page

371

Last Page

396

ISSN

1066-8888

Identifier

10.1007/s00778-010-0200-z

Publisher

Springer Verlag

Additional URL

http://dx.doi.org/10.1007/s00778-010-0200-z

Download

Share

COinS