Scaling Entity Resolution with K-Means: A Review of Partitioning Techniques

Entity resolution (ER) is a fundamental data integration process hindered by its quadratic computational complexity, making naive comparisons infeasible for large datasets. Blocking (or partitioning) is the foundational strategy to overcome this, traditionally using methods like K-Means clustering to group similar records. However, with the rise of deep learning and high-dimensional vector embeddings, the ER task has evolved into a vector similarity search problem. This review traces the evolution of K-Means from a direct, standalone blocking algorithm into a core partitioning engine within modern Approximate Nearest Neighbor (ANN) indexes. We analyze how its role has been adapted and optimized in partition-based systems like the Inverted File (IVF) system and Google’s SCANN, which are now central to scalable, embedding-based ER. By examining the architectural principles and trade-offs of these methods and contrasting them with non-partitioning alternatives like HNSW, this paper provides a coherent narrative on the journey of K-Means from a simple clustering tool to a critical component for scaling modern ER workflows.