Title

Continuous Visible Nearest Neighbour Queries

Publication Type

Conference Proceeding Article

Publication Date

3-2009

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, a CVNN query returns a set of (p, R) tuples such that p ? P is the nearest neighbor (NN) to every point r along the interval R ? q as well as p is 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 this paper, we formulate the problem and propose efficient algorithms for CVNN query processing, assuming that both P and O are indexed by R-trees. In addition, we extend our techniques to several variations of the CVNN query. Extensive experiments verify the efficiency and effectiveness of our proposed algorithms using both real and synthetic datasets.

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Management and Analytics

Publication

Proceedings of the 12th International Conference on Extending Database Technology EDBT '09, Saint Petersburg, March 24-26, 2009: Proceedings

First Page

144

Last Page

155

ISBN

9781605584225

Identifier

10.1145/1516360.1516378

Publisher

ACM

City or Country

St Petersburg

Additional URL

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