ing-bank/sparse_dot_topn

What it solves

比較非常大的特徵向量以尋找最佳匹配項時，通常需要執行稀疏矩陣乘法，接著進行前 n 個結果的選擇。標準方法在處理海量數據集時，可能會非常耗費記憶體且速度緩慢。本專案提供了一個高效能、並行化的實作，將前 n 個結果的選擇直接整合到乘法過程中，以減少記憶體佔用並提升速度。

How it works

該函式庫使用帶有 OpenMP 並行化技術的 C++ 擴充功能。它支援 CSR, CSC, 和 COO 稀疏矩陣格式（將後兩者轉換為 CSR 以進行處理）。在內部，它採用了 max-heap（最大堆積）來收集前 n 個值，將選擇的複雜度從 $O(n ext{ columns})$ 降低至 $O(top ext{-}n)$。使用者也可以應用一個閾值來過濾掉低值結果，或指定一個預期的密度來優化記憶體預分配。

Who it’s for

處理大型稀疏數據集（例如 TF-IDF 矩陣）的資料科學家和工程師，他們需要高效地檢索 Top-k 最相似的項目，或是在大規模尺度下進行高維度向量比對。

Highlights

• Integrated Top-N Selection: 整合了前 n 個結果的選擇功能，將乘法與選擇一步完成以節省記憶體。
• 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 倍。