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