Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/41036
Title: Two ellipse-based pruning methods for group nearest neighbor queries
Authors: Li, H.
Huang, B.
Lu, H. 
Huang, Z. 
Keywords: GNN
Group nearest neighbor query
Query optimization
Issue Date: 2005
Source: Li, H.,Huang, B.,Lu, H.,Huang, Z. (2005). Two ellipse-based pruning methods for group nearest neighbor queries. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems : 192-199. ScholarBank@NUS Repository.
Abstract: Group nearest neighbor (GNN) queries are a relatively new type of operations in spatial database applications. Different from a traditional κNN query which specifies a single query point only, a GNN query has multiple query points. Because of the number of query points and their arbitrary distribution in the data space, a GNN query is much more complex than a κNN query. In this paper, we propose two pruning strategies for GNN queries which take into account the distribution of query points. Our methods employ an ellipse to approximate the extent of multiple query points, and then derive a distance or minimum bounding rectangle (MBR) using that ellipse to prune intermediate nodes in a depth-first search via an R*-tree. These methods are also applicable to the best-first traversal paradigm. We conduct extensive performance studies. The results show that the proposed pruning strategies are more efficient than the existing methods. Copyright 2005 ACM.
Source Title: GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
URI: http://scholarbank.nus.edu.sg/handle/10635/41036
Appears in Collections:Staff Publications

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

Page view(s)

60
checked on Jan 21, 2018

Google ScholarTM

Check


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