A Streaming Algorithm for k-Means with Approximate Coreset

Min Li (), Dachuan Xu (), Dongmei Zhang and Tong Zhang ()
Additional contact information
Min Li: School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P. R. China
Dachuan Xu: Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing 100124, P. R. China
Dongmei Zhang: School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, P. R. China
Tong Zhang: Department of Information and Operations Research, College of Applied Sciences, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing 100124, P.R. China

Asia-Pacific Journal of Operational Research (APJOR), 2019, vol. 36, issue 01, 1-18

Abstract: For computing the k-means clustering of the streaming and distributed big sparse data, we present an algorithm to obtain the sparse coreset for the k-means in polynomial time. This algorithm is mainly based on the explicit form of the center of mass and the approximate k-means. Because of the existence of the approximation, the coreset of the output inevitably has a factor, which can be controlled to be a very small constant.

Keywords: k-Means clustering; coreset; streaming; approximation algorithm (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595919500064
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:36:y:2019:i:01:n:s0217595919500064

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595919500064

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().