Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39368
Title: A fast filter for obstructed nearest neighbor queries
Authors: Xia, C.
Hsu, D. 
Tung, A.K.H. 
Issue Date: 2004
Source: Xia, C.,Hsu, D.,Tung, A.K.H. (2004). A fast filter for obstructed nearest neighbor queries. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3112 : 203-215. ScholarBank@NUS Repository.
Abstract: In this paper, we study the Obstructed Nearest Neighbor (ONN) problem: given a set of points and a set of polygonal obstacles in two dimensions, find the k nearest neighbors to a query point according to the length of the shortest obstacle-avoiding path between two points. ONN query is useful both as a standalone tool in geographical information systems and as a primitive for spatial data analysis such as clustering and classification in the presence of obstacles. We propose an efficient ONN algorithm that processes only the data points and obstacles relevant to the query in an incremental way and thus filters out a large number of points and obstacles. Experiments on spatial data sets show the algorithm scales well with respect to the input data size and the number of nearest neighbors requested. © Springer-Verlag 2004.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/39368
ISSN: 03029743
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

76
checked on Dec 15, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.