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

arXiv: https://arxiv.org/abs/2412.02244 · HTML: https://mlsanity.com/paper/2412.02244/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 68 references that are in the map.
- First posted on arXiv 3 Dec 2024.

## Builds on (most cited first, 2 of 2)

- [Argoverse 2: Next Generation Datasets for Self-Driving Perception and Forecasting](https://mlsanity.com/paper/2301.00493/) (2023)
- [An Analysis of Deep Neural Network Models for Practical Applications](https://mlsanity.com/paper/1605.07678/) (2016)

## Abstract (arXiv)

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 computational 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 106, Dask-means uses less than 30MB of memory, 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 estimates the memory cost with a difference of less than 3% from the actual ones and predicts runtime with an MSE up to 33.3% lower than SOTA methods.