Monitoring k-nearest neighbor queries over moving objects
By Xiaohui Yu, Ken Q. Pu, Nick Koudas. IEEE International Conference on Data Engineering, 2005
366 citations recorded by the source corpus.
Many location-based applications require constant monitoring of k-nearest neighbor (k-NN) queries over moving objects within a geographic area. Existing approaches to this problem have focused on predictive queries, and relied on the assumption that the trajectories of the objects are fully predictable at query processing time. We relax this assumption, and propose two efficient and scalable algorithms using grid indices. One is based on indexing objects, and the other on queries. For each approach, a cost model is developed, and a detailed analysis along with the respective applicability is presented. The object-indexing approach is further extended to multi-levels to handle skewed data. We show by experiments that our grid-based algorithms significantly outperform R-tree-based solutions. Extensive experiments are also carried out to study the properties and evaluate the performance of the proposed approaches under a variety of settings.
Subfields: Computer Networks and Communications, Information Systems, Signal Processing
View Paper: https://www.semanticscholar.org/paper/642dcd84bcc9993f64713285d8f38bea07cbaa80
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
In Information Systems
In Signal Processing
Citations in the corpus
- The new Casper: query processing for location services without compromising privacy (2006, background): “Supporting continuous queries and large numbers of outstanding queries can be achieved by seamless integration of the Casper framework into any scalable and/or incremental location-based query processor (e.g., see [22, 25, 36, 34, 47, 48, 49]).”