Journal article

Incremental Evaluation of Visible Nearest Neighbor Queries

Sarana Nutanong, Egemen Tanin, Rui Zhang

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING | IEEE COMPUTER SOC | Published : 2010

Abstract

In many applications involving spatial objects, we are only interested in objects that are directly visible from query points. In this paper, we formulate the visible k nearest neighbor (VkNN) query and present incremental algorithms as a solution, with two variants differing in how to prune objects during the search process. One variant applies visibility pruning to only objects, whereas the other variant applies visibility pruning to index nodes as well. Our experimental results show that the latter outperforms the former. We further propose the aggregate VkNN query that finds the visible k nearest objects to a set of query points based on an aggregate distance function. We also propose tw..

View full abstract

Grants

Awarded by the Australian Research Council


Funding Acknowledgements

This work is partially supported under the Australian Research Council's Discovery funding scheme ( project number DP0880215).