The computation of the all-nearest-neighbors KNN is the bottleneck in UMAP and TSNE and both of these algorithms can get away with using approximate neighbors as the number of points grows very large.
We should investigate using approximate nearest neighbors functions within UMAP and TSNE, for example using nn-descent from RAFT, and see how much we can improve overall performance. In general, the training performance of many approximate algorithms is proportional to the recall, so we look at both the speedup and the embedding quality and potentially look at sampling as the data size grows very large.
The computation of the all-nearest-neighbors KNN is the bottleneck in UMAP and TSNE and both of these algorithms can get away with using approximate neighbors as the number of points grows very large.
We should investigate using approximate nearest neighbors functions within UMAP and TSNE, for example using nn-descent from RAFT, and see how much we can improve overall performance. In general, the training performance of many approximate algorithms is proportional to the recall, so we look at both the speedup and the embedding quality and potentially look at sampling as the data size grows very large.