Please use this identifier to cite or link to this item:
Title: Continuous k-means monitoring over moving objects
Authors: Zhang, Z. 
Yang, Y.
Tung, A.K.H. 
Papadias, D.
Keywords: k-means, continuous monitoring, query processing
Issue Date: 2008
Citation: Zhang, Z., Yang, Y., Tung, A.K.H., Papadias, D. (2008). Continuous k-means monitoring over moving objects. IEEE Transactions on Knowledge and Data Engineering 20 (9) : 1205-1216. ScholarBank@NUS Repository.
Abstract: Given a data set P, a k-means query returns k points in space (called centers), such that the average squared distance between each point in P and its nearest center is minimized. Since this problem is NP-hard, several approximate algorithms have been proposed and used in practice. In this paper, we study continuous k-means computation at a server that monitors a set of moving objects. Reevaluating k-means every time there is an object update imposes a heavy burden on the server (for computing the centers from scratch) and the clients (for continuously sending location updates). We overcome these problems with a novel approach that significantly reduces the computation and communication costs, while guaranteeing that the quality of the solution, with respect to the reevaluation approach, is bounded by a user-defined tolerance. The proposed method assigns each moving object a threshold (i.e., range) such that the object sends a location update only when it crosses the range boundary. First, we develop an efficient technique for maintaining the k-means. Then, we present mathematical formulas and algorithms for deriving the individual thresholds. Finally, we justify our performance claims with extensive experiments. © 2008 IEEE.
Source Title: IEEE Transactions on Knowledge and Data Engineering
ISSN: 10414347
DOI: 10.1109/TKDE.2008.54
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Dec 7, 2019


checked on Nov 28, 2019

Page view(s)

checked on Dec 2, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.