2005 · 57 citations · 13 references
ComputingComputer ScienceAlgorithmsDatabasesGeographic Information SystemsNearest Neighbor SearchQuery OptimizationQuery ProcessingSearching AlgorithmsSpatial Database SystemsSpatial DatabasesDepth-first SearchNearest Neighbor QueriesProximity QueriesPruningR* TreesR-treesSpatial Database ManagementSpatial Query Processing
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.
13
The R*-tree: an efficient and robust access method for points and rectangles
Norbert Beckmann, Hans‐Peter Kriegel, Ralf Schneider et al. · 1990 · 4.2K citations · Full text
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Sunil Arya, David M. Mount, Nathan S. Netanyahu et al. · Journal of the ACM · 1998 · 2.3K citations · Full text
Fast subsequence matching in time-series databases
Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos · 1994 · 1.7K citations · Full text
Nick Roussopoulos, Stephen Kelley, F. Vincent · 1995 · 1.4K citations · Full text