TY - GEN
T1 - Streaming k-means clustering with fast queries
AU - Zhang, Yu
AU - Tangwongsan, Kanat
AU - Tirthapura, Srikanta
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/5/16
Y1 - 2017/5/16
N2 - We present methods for k-means clustering on a stream with a focus on providing fast responses to clustering queries. Compared to the current state-of-The-Art, our methods provide substantial improvement in the query time for cluster centers while retaining the desirable properties of provably small approximation error and low space usage. Our algorithms rely on a novel idea of "coreset caching" that systematically reuses coresets (summaries of data) computed for recent queries in answering the current clustering query. We present both theoretical analysis and detailed experiments demonstrating their correctness and efficiency.
AB - We present methods for k-means clustering on a stream with a focus on providing fast responses to clustering queries. Compared to the current state-of-The-Art, our methods provide substantial improvement in the query time for cluster centers while retaining the desirable properties of provably small approximation error and low space usage. Our algorithms rely on a novel idea of "coreset caching" that systematically reuses coresets (summaries of data) computed for recent queries in answering the current clustering query. We present both theoretical analysis and detailed experiments demonstrating their correctness and efficiency.
UR - https://www.scopus.com/pages/publications/85021199328
U2 - 10.1109/ICDE.2017.102
DO - 10.1109/ICDE.2017.102
M3 - Conference contribution
AN - SCOPUS:85021199328
T3 - Proceedings - International Conference on Data Engineering
SP - 449
EP - 460
BT - Proceedings - 2017 IEEE 33rd International Conference on Data Engineering, ICDE 2017
PB - IEEE Computer Society
T2 - 33rd IEEE International Conference on Data Engineering, ICDE 2017
Y2 - 19 April 2017 through 22 April 2017
ER -