# GPU Semiring Primitives for Sparse Neighborhood Methods

arXiv: https://arxiv.org/abs/2104.06357 · HTML: https://mlsanity.com/paper/2104.06357/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 62 references that are in the map.
- First posted on arXiv 13 Apr 2021.

## Builds on (most cited first, 14 of 14)

- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Accounting for Variance in Machine Learning Benchmarks](https://mlsanity.com/paper/2103.03098/) (2021)
- [Sparse GPU Kernels for Deep Learning](https://mlsanity.com/paper/2006.10901/) (2020)
- [Machine Learning in Python: Main developments and technology trends in data science, machine learning, and artificial intelligence](https://mlsanity.com/paper/2002.04803/) (2020)
- [SpArch: Efficient Architecture for Sparse Matrix Multiplication](https://mlsanity.com/paper/2002.08947/) (2020)
- [Accelerating Sparse DNN Models without Hardware-Support via Tile-Wise Sparsity](https://mlsanity.com/paper/2008.13006/) (2020)
- [BiQGEMM: Matrix Multiplication with Lookup Table For Binary-Coding-based Quantized DNNs](https://mlsanity.com/paper/2005.09904/) (2020)
- [Bringing UMAP Closer to the Speed of Light with GPU Acceleration](https://mlsanity.com/paper/2008.00325/) (2020)
- [Accelerating Sparse Matrix-Matrix Multiplication with GPU Tensor Cores](https://mlsanity.com/paper/2009.14600/) (2020)
- [GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU](https://mlsanity.com/paper/1908.01407/) (2019)
- [Standards for Graph Algorithm Primitives](https://mlsanity.com/paper/1408.0393/) (2014)
- [A Dynamic Hash Table for the GPU](https://mlsanity.com/paper/1710.11246/) (2017)
- [Analysing the Performance of GPU Hash Tables for State Space Exploration](https://mlsanity.com/paper/1712.09494/) (2017)
- [Data embedding and prediction by sparse tropical matrix factorization](https://mlsanity.com/paper/2012.05210/) (2020)

## Built on by (most cited first, 3 of 3)

- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [FastSTMF: Efficient tropical matrix factorization algorithm for sparse data](https://mlsanity.com/paper/2205.06619/) (2022)
- [The Ubiquitous Sparse Matrix-Matrix Products](https://mlsanity.com/paper/2508.04077/) (2025)

## Abstract (arXiv)

High-performance primitives for mathematical operations on sparse vectors must deal with the challenges of skewed degree distributions and limits on memory consumption that are typically not issues in dense operations. We demonstrate that a sparse semiring primitive can be flexible enough to support a wide range of critical distance measures while maintaining performance and memory efficiency on the GPU. We further show that this primitive is a foundational component for enabling many neighborhood-based information retrieval and machine learning algorithms to accept sparse input. To our knowledge, this is the first work aiming to unify the computation of several critical distance measures on the GPU under a single flexible design paradigm and we hope that it provides a good baseline for future research in this area. Our implementation is fully open source and publicly available as part of the RAFT library of GPU-accelerated machine learning primitives (https://github.com/rapidsai/raft).