ing-bank/sparse_dot_topn

What it solves

Comparing very large feature vectors to find the best matches often requires performing a sparse matrix multiplication followed by selecting the top-n results. Standard methods can be memory-intensive and slow when dealing with massive datasets. This project provides a high-performance, parallelized implementation that integrates the top-n selection directly into the multiplication process to reduce memory footprint and increase speed.

How it works

The library uses a C++ extension with OpenMP for parallelization. It supports CSR, CSC, and COO sparse matrix formats (converting the latter two to CSR for processing). Internally, it employs a max-heap to collect the top-n values, reducing the complexity of selection from $O(n\text{ columns})$ to $O(top\text{-}n)$. Users can also apply a threshold to filter out low-value results or specify an expected density to optimize memory pre-allocation.

Who it’s for

Data scientists and engineers working with large-scale sparse datasets (e.g., TF-IDF matrices) who need to efficiently retrieve the top-k most similar items or perform high-dimensional vector matching at scale.

Highlights

• Integrated Top-N Selection: Combines multiplication and selection into one step to save memory.
• Parallelized Execution: Utilizes multiple CPU cores via OpenMP.
• Flexible Formats: Supports 32-bit and 64-bit integers and floats across CSR, CSC, and COO formats.
• Cluster Distribution: Includes utilities like zip_sp_matmul_topn to split large matrices (10M+ rows) across a cluster and merge the results.
• High Performance: Up to 6x faster than standard methods on specific hardware (Apple M2 Pro) for large TF-IDF matrices.