Scaling Pairwise Relationships to Massive Datasets

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2180 papers192 conceptsfrozen 2026-10-04

In many domains of machine learning—from clustering and optimal transport to graph analysis and sequence alignment—the fundamental operation is the comparison of every data point to every other data point. This results in a "pairwise matrix" (affinity, distance, or cost) that captures the global structure of the data.

However, these matrices encounter a hard physical limit known as the quadratic memory bottleneck. Because the number of entries in an $N \times N$ matrix grows with the square of the number of samples ($O(N^2)$), a dataset of just one million points requires a trillion-entry matrix. Storing such a matrix in 32-bit precision would require 4 terabytes of RAM, far exceeding the capacity of modern GPUs and standard workstations.

The Quadratic Wall in Relational Learning

The necessity of storing full dissimilarity or affinity matrices is a recurring theme across diverse research areas. In unsupervised learning, Linli Xu and Dale Schuurmans noted that using equivalence matrices to represent data partitions creates a scalability barrier for large-scale applications Unsupervised and Semi-Supervised Multi-Class Support Vector Machines. Similarly, in computer vision, the SGPN framework for 3D point cloud segmentation is restricted by an $N \times N$ similarity matrix that limits the density of point clouds the network can process in a single pass SGPN: Similarity Group Proposal Network for 3D Point Cloud Instance Segmentation.

This bottleneck isn't just a matter of "waiting longer" for a computation to finish; it is a memory exhaustion event that prevents the algorithm from running at all. As Ehsan Elhamifar and S. Shankar Sastry demonstrate with their DS3 framework, even when computational complexity is linear, the quadratic memory requirement for the dissimilarity matrix itself remains the primary constraint for massive datasets Dissimilarity-Based Sparse Subset Selection.

Symbolic Matrices and Lazy Evaluation

One of the most effective ways to bypass the quadratic wall is to stop treating the matrix as a static block of memory and start treating it as a dynamic computation. This is the core intuition behind symbolic matrices.

Instead of pre-calculating and storing all $N^2$ values, researchers like Jean Feydy and Michael M. Bronstein developed the KeOps library Fast geometric learning with symbolic matrices. KeOps performs "lazy evaluation," where matrix entries are computed on-the-fly during the reduction step (like a sum or a minimum). By fusing the distance calculation directly with the reduction kernel in CUDA, the software eliminates the need to store the intermediate $N \times N$ matrix entirely, reducing memory overhead from $O(N^2)$ to $O(N)$.

Low-Rank and Sparse Approximations

When the full matrix cannot be avoided, researchers look for ways to compress it without losing the underlying signal. This often involves exploiting the fact that real-world data usually lives on a low-dimensional manifold, meaning the $N \times N$ matrix is highly redundant.

Vector-Based and Incremental Processing

Another strategy involves changing the data structure of the algorithm itself. For example, in time-series analysis, the IncDTW package transforms Dynamic Time Warping—traditionally an $O(N^2)$ operation—into a vector-based approach. By calculating distances incrementally, it reduces space complexity to linear ($O(N)$), enabling the processing of live data streams IncDTW: An R Package for Incremental Calculation of Dynamic Time Warping.

Similarly, "centerless" clustering frameworks like FKMWC reformulate the clustering objective to rely on manifold learning rather than explicit centroid-to-point distance matrices, aiming to mitigate the scalability bottlenecks inherent in traditional fuzzy k-means Fuzzy K-Means Clustering without Cluster Centroids.

By moving away from dense, static matrix representations toward symbolic, low-rank, or sparse alternatives, this research direction enables the application of sophisticated relational algorithms to the "web-scale" datasets common in modern machine learning.

Papers in this version

Showing 60 of 180 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 173 papers
  2. Version 1 · 2026-10-04 · 180 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_quadratic_memory_bottleneck_ffc6a385,
  title = {quadratic memory bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-memory-bottleneck/rdr_ffc6a3859983446a9ebc1cb61ecc9933},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_scaling_pairwise_relationships_to_massiv_ffc6a385_v1,
  title = {Scaling Pairwise Relationships to Massive Datasets},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-pairwise-relationships-to-massive-datasets/rdr_ffc6a3859983446a9ebc1cb61ecc9933/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}