Campus Units
Computer Science, Electrical and Computer Engineering
Document Type
Article
Publication Version
Accepted Manuscript
Publication Date
8-24-2020
Journal or Book Title
IEEE Transactions on Knowledge and Data Engineering
DOI
10.1109/TKDE.2020.3018744
Abstract
We present new algorithms for k-means clustering on a data stream with a focus on providing fast responses to clustering queries. Compared to the state-of-the-art, our algorithms provide substantial improvements in the query time for cluster centers while retaining the desirable properties of provably small approximation error and low space usage. Our proposed clustering algorithms systematically reuse the "coresets" (summaries of data) computed for recent queries in answering the current clustering query, a novel technique which we refer to as coreset caching. We also present an algorithm called OnlineCC that integrates the coreset caching idea with a simple sequential streaming k-means algorithm. In practice, OnlineCC algorithm can provide constant query time. We present both theoretical analysis and detailed experiments demonstrating the correctness, accuracy, and efficiency of all our proposed clustering algorithms.
Rights
© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Copyright Owner
IEEE
Copyright Date
2020
Language
en
File Format
application/pdf
Recommended Citation
Zhang, Yu; Tangwongsan, Kanat; and Tirthapura, Srikanta, "Fast Streaming k-Means Clustering with Coreset Caching" (2020). Electrical and Computer Engineering Publications. 257.
https://lib.dr.iastate.edu/ece_pubs/257
Comments
This is a manuscript of an article published as Zhang, Yu, Kanat Tangwongsan, and Srikanta Tirthapura. "Fast Streaming k-Means Clustering with Coreset Caching." IEEE Transactions on Knowledge and Data Engineering (2020). DOI: 10.1109/TKDE.2020.3018744. Posted with permission.