Skip to main content
Article
Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring
SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on management of data
  • Kyriakos MOURATIDIS, Hong Kong University of Science and Technology
  • Marios Hadjieleftheriou
  • Dimitris Papadias, Hong Kong University of Science and Technology
Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
6-2005
Abstract

Given a set of objects P and a query point q, a k nearest neighbor (k-NN) query retrieves the k objects in P that lie closest to q. Even though the problem is well-studied for static datasets, the traditional methods do not extend to highly dynamic environments where multiple continuous queries require real-time results, and both objects and queries receive frequent location updates. In this paper we propose conceptual partitioning (CPM), a comprehensive technique for the efficient monitoring of continuous NN queries. CPM achieves low running time by handling location updates only from objects that fall in the vicinity of some query (and ignoring the rest). It can be used with multiple, static or moving queries, and it does not make any assumptions about the object moving patterns. We analyze the performance of CPM and show that it outperforms the current state-of-the-art algorithms for all problem settings. Finally, we extend our framework to aggregate NN (ANN) queries, which monitor the data objects that minimize the aggregate distance with respect to a set of query points (e.g., the objects with the minimum sum of distances to all query points).

ISBN
9781595930606
Identifier
10.1145/1066157.1066230
Publisher
ACM
City or Country
Baltimore, MD
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Additional URL
http://dx.doi.org/10.1145/1066157.1066230
Citation Information
Kyriakos MOURATIDIS, Marios Hadjieleftheriou and Dimitris Papadias. "Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring" SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on management of data (2005) p. 634 - 645
Available at: http://works.bepress.com/kyriakos_mouratidis/16/