Please use this identifier to cite or link to this item:
|dc.title||A fast filter for obstructed nearest neighbor queries|
|dc.identifier.citation||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.|
|dc.description.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.|
|dc.description.sourcetitle||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Appears in Collections:||Staff Publications|
Show simple item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.