|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/6001
|
| Title: | Continuous k-means monitoring over moving objects |
| Authors: | Zhang, Zhenjie
Yang, Yin
Tung, Anthony K. H.
Papadias, Dimitris |
| Keywords: | k-means
Continuous monitoring
Query processing |
| Issue Date: | 2008 |
| Citation: | IEEE Transactions on Knowledge and Data Engineering, v. 20, no. 9, September 2008, p. 1205-1216 |
| Abstract: | Given a dataset 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. Re-evaluating 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 re-evaluation 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 formulae and algorithms for deriving the individual thresholds. Finally, we justify our performance claims with extensive experiments. |
| Rights: | © 2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder. |
| URI: | http://hdl.handle.net/1783.1/6001 |
| Appears in Collections: | CSE Journal/Magazine Articles
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| TKDE08-KM.pdf | pre-published version | 577Kb | Adobe PDF | View/Open |
|
Find published version via |
All items in this Repository are protected by copyright, with all rights reserved.
|
