ing-bank/sparse_dot_topn

What it solves

非常に大きな特徴量ベクトルを比較して最適なマッチングを見つけるには、通常、疎行列乗算を実行し、その後に Top-n 結果の選択を行なう必要があります。標準的な手法では、大規模なデータセットを扱う際、メモリ消費量が多く、速度が遅いという課題があります。本プロジェクトは、乗算プロセスに Top-n 選択を直接統合することで、メモリ使用量を抑え、速度を向上させる高性能で並列化された実装を提供します。

How it works

本ライブラリは、OpenMP を用いた C++ 拡張機能を使用しています。CSR, CSC, および COO 疎行列形式をサポートしています（後者二つは処理のために CSR に変換されます）。内部的には、max-heap を使用して Top-n 値を収集し、選択の計算量複素度を $O(n ext{ columns})$ から $O(top ext{-}n)$ に削減します。また、ユーザーは閾値を使用して低価値の結果をフィルタリングしたり、期待される密度を計算してメモリの事前割り当てを最適化したりすることも可能です。

Who it’s for

大規模な疎行列データセット（例：TF-IDF 行列）を扱い、Top-k 最も類似したアイテムを効率的に取得、または高次元ベクトルマッチングを大規模に行う必要があるデータサイエンティストやエンジニア。

Highlights

• Integrated Top-N Selection: 乗算と選択を一つのステップに組み合わせることで、メモリを節約します。
• Parallelized Execution: OpenMP を介して複数の CPU コアを利用します。
• Flexible Formats: CSR, CSC, および COO 形式において、32-bit および 64-bit 整数と浮動小数点数に対応しています。
• Cluster Distribution: zip_sp_matmul_topn のようなユーティリティを含み、大規模な行列（10M+ 行）を分割してクラスターへ分散し、クラスターの結果を結果として結合します。
• High Performance: 特定のハードウェア（Apple M2 Pro）において、大規模な TF-IDF 行列に対して標準的な手法より最大 6 倍高速です。