ACM International Conference on Multimedia (ACMMM) 2018

再構成可能な転置インデクス

松井勇佑
国立情報学研究所
日並遼太
東京大学
佐藤真一
国立情報学研究所

部分集合に対する探索．対象のIDを指定することで部分集合探索を行います．探索結果は指定されたデータのみを含みます．

最適化された高速なANNシステムがあり，大量の新しいデータが追加されたとします．果たしてシステムは高速でしょうか？

Abstract

既存の近似最近傍探索手法には，実用上極めて重要ながら研究者からは注目されていない二つの基本的な問題があります． (1) まず，既存のシステムはデータベース全てに対する探索は高速に実行できますが，データセットの部分集合に対する検索を 行うことは難しいです．(2) 次に，新しいたくさんのデータがシステムに追加されたときに，性能がどう変化するについて議論がありません． これらを解決するために，私達は再構成可能な転置インデクス：Reconfigurable Inverted Index (Rii) を開発しました．標準的なIVFADCシステムをもとに，私達はデータが線形に保存されるようにシステムをレイアウトしました． これにより，もし部分集合が小さいときは探索手法をPQ線形探索に変更することで，効率的に部分集合に対する探索 を行うことが出来ます．またこの線形のレイアウトにより，新しいデータが追加されたときにも動的にデータ構造を 変化させることが出来，それにより高速な探索速度が保たれます． 比較実験により，Riiは最新のシステムであるFaissと同程度の性能であることが示されました．

Install

  • pip install rii

Publication

BibTeX

@inproceedings{acmmm_matsui_2018,
    author={Yusuke Matsui and Ryota Hinami and Shin'ichi Satoh},
    title={Reconfigurable Inverted Index},
    booktitle={ACM International Conference on Multimedia (ACMMM)},
    pages={1715--1723},
    year={2018}
}