2010/09/21 by Romain Tavenard, Tavenard, Romain, Laurent Amsaleg +4
Computer Science · Engineering · #Advanced Image and Video Retrieval Techniques #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #Image Retrieval and Classification Techniques #Remote-Sensing Image Classification #Robotics and Sensor-Based Localization #cs.CV
paper · pdf · doi:10.48550/arxiv.1009.4739
arxiv created 2010/09/21 · openalex publication_date 2010/09/21 · arxiv updated 2010/09/27 · openalex created_date 2025/10/27 · openalex updated_date 2026/07/28
Many algorithms for approximate nearest neighbor search in high-dimensional spaces partition the data into clusters. At query time, in order to avoid exhaustive search, an index selects the few (or a single) clusters nearest to the query point. Clusters are often produced by the well-known k-means approach since it has several desirable properties. On the downside, it tends to produce clusters having quite different cardinalities. Imbalanced clusters negatively impact both the variance and the expectation of query response times. This paper proposes to modify k-means centroids to produce clusters with more comparable sizes without sacrificing the desirable properties. Experiments with a large scale collection of image descriptors show that our algorithm significantly reduces the variance of response times without seriously impacting the search quality.