Back to Search
Start Over
Continuous κ-Means Monitoring over Moving Objects.
- Source :
- IEEE Transactions on Knowledge & Data Engineering; Sep2008, Vol. 20 Issue 9, p1205-1216, 12p, 4 Black and White Photographs, 20 Graphs
- Publication Year :
- 2008
-
Abstract
- Given a data set P, a κ-means query returns κ 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 κ-means computation at a server that monitors a set of moving objects. Reevaluating κ-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 κ-means. Then, we present mathematical formulas and algorithms for deriving the individual thresholds. Finally, we justify our performance claims with extensive experiments. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10414347
- Volume :
- 20
- Issue :
- 9
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Knowledge & Data Engineering
- Publication Type :
- Academic Journal
- Accession number :
- 34090199
- Full Text :
- https://doi.org/10.1109/TKDE.2008.54