概要

本研究では，10億個程度あっても高速に動作する，PQk-meansというクラスタリング手法を提案する．提案手法では，事前に入力ベクトルを直積量子化コードに圧縮し，圧縮された世界で処理を行うことで，高次元データに対しても高速かつ省メモリでクラスタリングを実行する．k-meansと同様に，PQk-meansは「割り付けステップ」と「更新ステップ」を繰り返し，どちらのステップも，圧縮された次元で処理を行う．本研究の評価実験では，データ一個のベクトルを32bitに圧縮しても，k-meansに近い精度を達成できることを示した．提案手法により，10億個の128次元SIFTベクトルをK=10万個に分割する処理を，わずか14時間で，かつ32GB以下のメモリ使用量の通常のコンピュータ一台で実行できた．

bibtex

@inproceedings{acmmm_matsui_2017,
  author = {Yusuke Matsui and Keisuke Ogaki and Toshihiko Yamasaki and Kiyoharu Aizawa},
  booktitle = {ACM International Conference on Multimedia (ACMMM)},
  title = {PQk-means: Billion-scale Clustering for Product-quantized Codes},
  pages = {1725--1733},
  year = {2017}
}

発表リスト

• “PQk-means: Billion-scale Clustering for Product-quantized Codes”, ACM Multimedia (ACMMM), 2017.