loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Incremental Evaluation of Visible Nearest Neighbor Queries
PrePrint
ISSN: 1041-4347
Sarana Nutanong, University of Melbourne, Victoria
Egemen Tanin, University of Melbourne, Victoria
Rui Zhang, University of Melbourne, Victoria
In many applications involving spatial objects, we are only interested in objects that are directly visible from query points. In this article, 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, which finds the visible k nearest objects to a set of query points based on an aggregate distance function. We also propose two approaches to processing the aggregate VkNN query. One accesses the database via multiple VkNN queries, whereas the other issues an aggregate k nearest neighbor query to retrieve objects from the database and then re-rank the results based on the aggregate visible distance metric. With extensive experiments, we show that the latter approach consistently outperforms the former one.
Index Terms:
Spatial databases, Spatial databases and GIS
Citation:
Sarana Nutanong, Egemen Tanin, Rui Zhang, "Incremental Evaluation of Visible Nearest Neighbor Queries," IEEE Transactions on Knowledge and Data Engineering, 02 Jul. 2009. IEEE computer Society Digital Library. IEEE Computer Society, <http://doi.ieeecomputersociety.org/10.1109/TKDE.2009.158>
Usage of this product signifies your acceptance of the Terms of Use.