On Simplifying Large-Scale Spatial Vectors: Fast, Memory-Efficient, and Cost-Predictable $k$-Means

The$k$-means algorithm can simplify large-scale spatial vectors, such as 2D geo-Locations and 3D point clouds, to support fast analytics and learning. However, when processing large-scale datasets, existing$k$-means algorithms have been developed to achieve high performance with significant compu-tational resources, such as memory and CPU usage time. These algorithms, though effective, are not well-suited for resource-constrained devices. In this paper, we propose a fast, memory-efficient, and cost-predictable$k$-means called Dask-means. We first accelerate$k$-means by designing a memory-efficient accelerator, which utilizes an optimized nearest neighbor search over a memory-tunable index to assign spatial vectors to clusters in batches. We then design a lightweight cost estimator to predict the memory cost and runtime of the k-means task, allowing it to request appropriate memory from devices or adjust the accelerator's required space to meet memory constraints, and ensure sufficient CPU time for running k-means. Experiments show that when simplifying datasets with scale such as$10^{6}$, Dask-means uses less than 30MB of memory, and achieves over 168 times speedup compared to the widely-used Lloyd's algorithm. We also validate Dask-means on mobile devices, where it demonstrates significant speedup and low memory cost compared to other state-of-the-art (SOTA)$k$-means algorithms. Our cost estimator achieves a memory cost estimation error with a difference of less than 3% from the actual ones and an MSE for predicted runtime at least 52.1 % lower than SOTA methods.