Paper Info
Title
knor: A NUMA-Optimized In-Memory, Distributed and Semi-External-Memory k-means Library.
Abstract
k-means is one of the most influential and utilized machine learning algorithms. Its computation limits the performance and scalability of many statistical analysis and machine learning tasks. We rethink and optimize k-means in terms of modern NUMA architectures to develop a novel parallelization scheme that delays and minimizes synchronization barriers. The k-means NUMA Optimized Routine knor) library has (i) in-memory knori), (ii) distributed memory (knord), and (ii) semi-external memory (\\textsf{knors}) modules that radically improve the performance of k-means for varying memory and hardware budgets. knori boosts performance for single machine datasets by an order of magnitude or more. \\textsf{knors} improves the scalability of k-means on a memory budget using SSDs. knors scales to billions of points on a single machine, using a fraction of the resources that distributed in-memory systems require. knord retains knori's performance characteristics, while scaling in-memory through distributed computation in the cloud. knor modifies Elkan's triangle inequality pruning algorithm such that we utilize it on billion-point datasets without the significant memory overhead of the original algorithm. We demonstrate knor outperforms distributed commercial products like H2O, Turi (formerly Dato, GraphLab) and Spark's MLlib by more than an order of magnitude for datasets of 107 to 109 points.
Year
DOI
Venue
2017
10.1145/3078597.3078607
HPDC
Field
DocType
Citations 
k-means clustering,Synchronization,Spark (mathematics),Computer science,Parallel computing,Distributed memory,Real-time computing,Cluster analysis,Cloud computing,Scalability,Distributed computing,Auxiliary memory
Conference
1
PageRank 
References 
Authors
0.35
24
5
Name
Order
Citations
PageRank
Disa Mhembere1635.42
Da Zheng2958.61
Carey E. Priebe3505108.56
Joshua T. Vogelstein427331.99
Randal Burns51955115.15