A Flexible K-Means Operator for Hybrid Databases

The K-means algorithm is widely used in unsupervised learning and data exploration. It is less used in analytical databases due to its high computational cost. K-means has been explored in great detail, mostly focusing on performance. However, in emerging hybrid CPU-FPGA databases where memory bandwidth is shared across software and hardware operators, two additional requirements arise. One is parameterization to avoid frequent reprogramming. The other is concurrent use to balance memory bandwidth and computation. Our design supports two operational modes that can be chosen at runtime, one for high query throughput and one for evaluating multiple clusters concurrently. The former targets speed up, while the latter targets efficient bandwidth utilization by increasing the amount of computation per input byte. Our design is competitive when compared to both existing FPGA-based solutions as well as highly optimized multi-core software implementations.