Uniform Manifold Approximation and Projection (UMAP) is a dimensionality reduction technique widely used for visualization and feature extraction. Applications range across exploratory data analysis, topic modeling, and single-cell analysis. Many of these workflows are iterative and exploratory, requiring UMAP to be run repeatedly as users analyze their data or tune parameters. As datasets grow, the cost of each UMAP run increases substantially, making interactive exploration and iterative analysis increasingly difficult.

A critical step in the UMAP algorithm is the construction of an all-neighbors kNN graph over the dataset, which finds the k-nearest neighbors for every vector in the dataset.…