Nearest neighborhood search in spatial databases
Authors:
- 1 April 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 699-710
Abstract
This paper proposes a group version of the nearest neighbor (NN) query, called the nearest neighborhood (NNH) query, which aims to find the nearest group of points, instead of one nearest point. Given a set O of points, a query point q, and a ρ-radius circle C, the NNH query returns the nearest placement of C to q such that there are at least k points enclosed by C. We present a fast algorithm for processing the NNH query based on the incremental retrieval of nearest neighbors using the R-tree structure on O. Our solution includes several techniques, to efficiently maintain sets of retrieved nearest points and identify their validities in terms of the closeness constraint of their points. These techniques are devised from the unique characteristics of the NNH search problem. As a side product, we solve a new geometric problem, called the nearest enclosing circle (NEC) problem, which is of independent interest. We present a linear expected-time algorithm solving the NEC problem using the properties of the NEC similar to those of the smallest enclosing circle. We provide extensive experimental results, which show that our techniques can significantly improve the query performance.Keywords
This publication has 21 references indexed in Scilit:
- Nearest group queries2013
- Collective spatial keyword queries2013
- A scalable algorithm for maximizing range sum in spatial databasesProceedings of the VLDB Endowment, 2012
- Collective spatial keyword querying2011
- On Group Nearest Group Query ProcessingIEEE Transactions on Knowledge and Data Engineering, 2010
- Mining interesting locations and travel sequences from GPS trajectories2009
- A novel optimization approach to efficiently process aggregate similarity queries in metric access methods2008
- Computational Geometry2008
- Two ellipse-based pruning methods for group nearest neighbor queries2005
- Fundamentals of Convex Analysis2001