Two ellipse-based pruning methods for group nearest neighbor queries

Hongga Li, Hua Lu, Bo Huang, Zhiyong Huang

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

Abstract

Group nearest neighbor (GNN) queries are a relatively new type of operations in spatial database applications. Different from a traditional kNN 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 kNN 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
OriginalsprogEngelsk
TitelGIS'05 Proceedings of the 13th ACM International Workshop on Geographic Information Systems : November 4-5, 2005, Bremen, Germany co-located with CIKM 2005
RedaktørerCyrus Shahabi, Omar Boucelma
Antal sider8
ForlagAssociation for Computing Machinery
Publikationsdato2005
Sider192-199
ISBN (Trykt)1-59593-146-5
DOI
StatusUdgivet - 2005
Udgivet eksterntJa
Begivenhed13th ACM international workshop on Geographic information systems: co-located with CIKM 2005 - Bremen, Tyskland
Varighed: 4 nov. 20055 nov. 2005
Konferencens nummer: 13

Konference

Konference13th ACM international workshop on Geographic information systems
Nummer13
Land/OmrådeTyskland
ByBremen
Periode04/11/200505/11/2005

Citer dette