Dwango Media Village(ドワンゴメディアヴィレッジ,dmv)

PQk-means: 10億個規模の直積量子化コードに対するクラスタリング

Dwango Media Village(ドワンゴメディアヴィレッジ,dmv)による PQk-means: 10億個規模の直積量子化コードに対するクラスタリング

概要

本研究では,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 = {Qk-means: Billion-scale Clustering for Product-quantized Codes},
  pages = {1725--1733},
  year = {2017}
}

発表リスト