PQk-means: Billion-scale Clustering for Product-quantized Codes

2017-09-12 · Yusuke Matsui, Keisuke Ogaki, Toshihiko Yamasaki, Kiyoharu Aizawa

Data clustering is a fundamental operation in data analysis. For handling large-scale data, the standard k-means clustering method is not only slow, but also memory-inefficient. We propose an efficient clustering method for billion-scale feature vectors, called PQk-means. By first compressing input vectors into short product-quantized (PQ) codes, PQk-means achieves fast and memory-efficient clustering, even for high-dimensional vectors. Similar to k-means, PQk-means repeats the assignment and update steps, both of which can be performed in the PQ-code domain. Experimental results show that even short-length (32 bit) PQ-codes can produce competitive results compared with k-means. This result is of practical importance for clustering in memory-restricted environments. Using the proposed PQk-means scheme, the clustering of one billion 128D SIFT features with K = 10^5 is achieved within 14 hours, using just 32 GB of memory consumption on a single computer.

📄 PDF Abstract BibTeX arXiv:1709.03708

Code (1)

DwangoMediaVillage/pqkmeans 공식 구현

Tasks

Clustering

Methods 이 논문이 사용한 방법론

k-Means Clustering k-Means Clustering is a clustering algorithm that divides a training set into $k$ different clusters of examples that are near each other. It works by initializing $k$…

Cartesian K-Means

2013-06-01 · CVPR 2013 6 · Mohammad Norouzi, David J. Fleet

A fundamental limitation of quantization techniques like the k-means clustering algorithm is the storage and runtime cost associated with the large numbers of clusters required to keep quantization errors small and model…

Clustering Object Recognition Quantization Retrieval

Vector Quantized Latent Concepts: A Scalable Alternative to Clustering-Based Concept Discovery

2026-02-02 · Xuemin Yu, Ankur Garg, Samira Ebrahimi Kahou, Hassan Sajjad arxiv

Large language models (LLMs) encode rich semantic information in their hidden states, yet it remains difficult to understand what information these internal representations capture. Latent concepts extracted from hidden …

Scaling Up Deep Clustering Methods Beyond ImageNet-1K

2024-06-03 · Nikolas Adaloglou, Felix Michels, Kaspar Senft, Diana Petrusheva 외

Deep image clustering methods are typically evaluated on small-scale balanced classification datasets while feature-based $k$-means has been applied on proprietary billion-scale datasets. In this work, we explore the per…

Clustering Deep Clustering Image Clustering

Web-Scale Image Clustering Revisited

2015-12-01 · ICCV 2015 12 · Yannis Avrithis, Yannis Kalantidis, Evangelos Anagnostopoulos, Ioannis Z. Emiris

Large scale duplicate detection, clustering and mining of documents or images has been conventionally treated with seed detection via hashing, followed by seed growing heuristics using fast search. Principled clustering …

Clustering Image Clustering Quantization

K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes

2013-06-01 · CVPR 2013 6 · Kaiming He, Fang Wen, Jian Sun

In computer vision there has been increasing interest in learning hashing codes whose Hamming distance approximates the data similarity. The hashing functions play roles in both quantizing the vector space and generating…

Clustering Quantization