High-dimensional datasets containing millions of samples or billions of features are now commonplace across biology, linguistics, and web-scale applications. To make sense of this data, researchers rely on dimensionality reduction (DR) techniques like Multidimensional Scaling (MDS), t-SNE, and UMAP to project complex spaces into interpretable 2D or 3D visualizations.
However, traditional DR algorithms hit a computational wall when scaled to modern datasets. Many of these methods exhibit quadratic ($O(N^2)$) or cubic ($O(N^3)$) time and memory complexities relative to the number of data points $N$. As a result, processing massive datasets on standard hardware frequently leads to memory exhaustion or intractable runtimes. As noted by Haiyang Huang in Towards a comprehensive evaluation of dimension reduction methods for transcriptomic data visualization, this creates a severe bottleneck where practitioners must often compromise between visualization quality and practical computational limits.
To bypass this bottleneck, modern research focuses on algorithmic approximations, distributed sketching, and hardware acceleration designed to break the quadratic scaling barrier.
The Landmark Solution: Approximating Global Geometry
The primary driver of quadratic complexity in manifold learning is the need to compute pairwise relationships between every single pair of data points. Landmark-based methods circumvent this by selecting a small, representative subset of $m$ "landmark" points ($m \ll N$). The algorithm computes exact pairwise distances only within this small subset, and then projects the remaining $N - m$ points based on their distances to the landmarks.
Traditional (O(N²)): [ All-to-All Pairwise Distances ]
Landmark (O(mN)): [ Landmarks (m) ] <---> [ All Data Points (N) ]
(Exact Pairs) (Approximated)
In FastMap, MetricMap, and Landmark MDS are all Nystrom Algorithms, John Platt provided a key theoretical insight into why this works: seemingly distinct landmark heuristics are actually variations of the Nyström approximation. The Nyström method approximates a large, positive semi-definite matrix (like a distance or kernel matrix) using a low-rank sample of its columns. This mathematical unification proves that we can reconstruct global data geometry with $O(m^2N)$ time complexity instead of $O(N^3)$.
This landmarking principle underpins several highly scalable algorithms:
- FEDRA: Developed by Panagis Magdalinos et al. in FEDRA: A Fast and Efficient Dimensionality Reduction Algorithm and expanded in Enhancing Clustering Quality through Landmark-Based Dimensionality Reduction, this approach uses landmarks to preserve pairwise distances efficiently, accelerating downstream tasks like clustering without sacrificing projection quality.
- ShapeVis: To scale topological data analysis to millions of points, Nupur Kumari et al. introduced ShapeVis (ShapeVis: High-dimensional Data Visualization at Scale), which pairs manifold landmarking with random-walk-based weighting to construct concise, structurally accurate graphs without encountering memory overflows.
Sketching and Distributed Aggregation
When datasets grow to billions of points, the data may be geographically distributed or too massive to fit onto a single machine's memory for landmark selection. In these scenarios, researchers use data "sketching" to compress data streams at the edge before performing dimensionality reduction.
In Sketch and Scale Geo-distributed tSNE and UMAP, Viska Wei et al. proposed the "Sketch and Scale" (SnS) framework. SnS utilizes Count Sketches—a sublinear-space data structure—to summarize high-dimensional data directly on distributed edge nodes. These compact sketches are then transmitted to a central coordinator and aggregated. Because the sketches preserve the underlying frequency and distance distributions of the massive dataset, standard algorithms like t-SNE or UMAP can be applied directly to the aggregated summary, unlocking the visualization of billions of data points.
Hardware Acceleration and Optimization Tuning
An alternative to approximating the data matrix is to accelerate the exact or near-exact computations using modern parallel hardware architectures like GPUs, alongside specialized optimization schedules.
To eliminate the days-long runtimes associated with CPU-based embedding algorithms, David Chan et al. developed t-SNE-CUDA (t-SNE-CUDA: GPU-Accelerated t-SNE and its Applications to Modern Data). The authors achieved 50–700x speedups by offloading the initial nearest-neighbor search to highly optimized GPU similarity libraries (such as FAISS) and parallelizing the subsequent force-directed gradient descent steps.
However, scaling to tens of millions of points introduces optimization challenges: the gradient descent can become unstable, causing the embedding to tear or collapse into poor local minima. To address this, Rita González-Márquez et al. designed an optimized pipeline in Two-dimensional visualization of large document libraries using t-SNE. By introducing "uniform affinities" to balance local densities and an "early exaggeration annealing" schedule, the authors successfully mapped the entire 19-million-paper PubMed database into a single cohesive 2D embedding, demonstrating that algorithmic parameter tuning is just as vital as raw hardware power for large-scale stability.
Scaling the Feature Dimension
Scalability bottlenecks do not only occur with the number of samples ($N$); they also emerge when the number of features or dimensions ($D$) scales into the millions or billions.
To handle extreme feature dimensionality without the computational overhead of traditional unsupervised models, Jiquan Ngiam et al. introduced Sparse Filtering (Sparse Filtering). Instead of attempting to explicitly model the complex joint data distribution, Sparse Filtering optimizes a simple objective: the sparsity of normalized feature representations. This optimization requires only a single tunable parameter and scales efficiently to high-resolution inputs.
For distributed feature spaces, Jun Suzuki et al. developed a semi-supervised optimization framework in Fused Feature Representation Discovery for High-Dimensional and Sparse Data. By leveraging MapReduce to distribute the optimization workload, the authors compressed billions of sparse, high-dimensional features into a handful of dense, "fused" features, proving that distributed computing paradigms can successfully mitigate the curse of dimensionality.
Key Foundational Work
FEDRA: A Fast and Efficient Dimensionality Reduction Algorithm (2009) — contributed 1 concept elements to this direction.
FastMap, MetricMap, and Landmark MDS are all Nystrom Algorithms (2005) — contributed 1 concept elements to this direction.