フラッシュメモリの効果的な導入と新アルゴリズムによる近似最近傍探索手法Locality Sensitive Hashingの高速化

2023年6月14日

データベース処理、テキスト検索、パターン認識など様々な用途において用いられている最近傍探索はアプリケーション性能を決める重要なデータ処理の一つです。厳密な最近傍探索は膨大な計算量が必要となるため、一般には近似的手法が用いられます。この近似的手法の一つとして、Locality Sensitive Hashing（LSH）があります。この手法は近似的手法ではあるものの成功確率が理論的に保証されているという他の近似手法にはない特徴を持ち、実践的なクエリ速度を達成できるため幅広く使われています。初期に提案されたLSHの一種であるE2LSH^[1]はクエリ（データベースの中から問い合わせ対象に近いオブジェクトを探す処理）に対する計算量が検索対象の総データ数に対してデータ数が多くなるほど計算量の伸びが鈍くなる劣線形という利点を持つものの、データインデックスサイズが逆に幾何級数的に大きくなる超線形であるデメリットを抱えていました。データインデックスがDRAMに格納できないほど大きいため、SSDやHDDなどの外部ストレージに置く必要があり、インデックスへのアクセスが大きな性能劣化を招いていました。その後のLSH研究（SRS^[2]など）は、データインデックスサイズを小さく保つ方向に進み、DRAMに格納可能なインデックスサイズにより理論保証を保ちつつ堅実な実行性能を達成しました。しかし、インデックスサイズは小さいものの（図1 (a)）クエリ計算量（図１ (b)）が検索対象の総データ数に対して劣線形という利点を失わなければなりませんでした。

今回、E2LSHをフラッシュメモリ活用に向けたアルゴリズム（E2LSH on Storage, 略称 E2LSHoS）を新開発し、データ総数10億個までの大規模データセット（データインデックスサイズ最大約7TB）に対して評価を行いました。E2LSHoS は並列読み出しが得意なSSDを活用するために、巨大なデータインデックスは外部ストレージに配し、処理すべきデータはメインメモリに配することにより、非同期アクセスおよび複数のクエリの並列実行を可能としました（図 2）。これにより劣線形クエリ速度の利点によって、データセット規模が大きくなるほど、LSH先行研究であるSRSより高い性能の達成が実現されました。また、このアルゴリズムの性能を実証する為、外部ストレージとして1つのCPUコアから1秒間に100万以上のストレージアクセスリクエストを発行できる、低レイテンシフラッシュXL-FLASH™を使用したデモドライブ^[3]を用い評価を行いました。E2LSHoS は優れた劣線形クエリ速度を達成すると共にDRAMにすべてを格納した理想的な E2LSH に相当する性能を実現しました。（図 3）。
本結果は、弊社低レイテンシフラッシュによる少計算量アルゴリズムをサポートした一例です。日々データ量が増大している近年において大容量データをより短時間で探索できるE2LSHoSの価値が高まっていると考えており、同様の性質を持つ他の有用なアルゴリズムに対しても適用できると考えています。