Optimal Transport (OT) is a highly effective mathematical framework for measuring the distance between probability distributions. However, it has historically suffered from a severe "weight" problem. Standard Wasserstein distance calculations are computationally heavy, scaling at $O(n^3 \log n)$, and fall victim to the curse of dimensionality, requiring an exponential number of samples to maintain accuracy as dimensions increase.
To mitigate this, researchers developed Sliced Wasserstein (SW) distance. SW projects high-dimensional data onto numerous random one-dimensional lines (slices). Because the Wasserstein distance has a simple, closed-form solution in 1D based on sorting data, SW reduces the computational burden to $O(n \log n)$. Yet, standard SW still requires storing all $n$ data points in memory to sort them. In the era of the Internet of Things (IoT) and real-time sensor networks, we frequently encounter infinite sequences of streaming data. We simply cannot afford to store everything.
How do we compute these distances on the fly with a strictly limited memory budget? This paper introduces Stream-SW, the first method to estimate SW distance directly from continuous data streams, achieving near-linear time complexity and logarithmic space complexity.
The Stream-SW Approach
Stream-SW bridges the gap between Sliced Optimal Transport and streaming quantile approximation by processing data in three steps:
- Slicing on the Fly: As data points arrive in the stream, they are immediately projected onto a set of $L$ random directions.
- Quantile Sketches: Instead of storing every projected point, Stream-SW utilizes the Karnin-Lang-Liberty (KKL) sketch. This compact data structure maintains a statistical summary of the data distribution. It uses "compactors" that periodically discard half of their data while doubling the weight of the remaining points, preserving statistical accuracy without ballooning memory.
- Streaming 1D Estimator: Because the 1D Wasserstein distance is defined by the difference between the quantile functions of two distributions, Stream-SW uses the KKL sketch to reconstruct these functions. It computes the distance without ever needing the full original dataset.
The core insight of this approach is realizing that 1D Wasserstein distance is entirely determined by quantiles. By leveraging decades of computer science research on streaming quantiles, Stream-SW limits memory growth to a logarithmic scale relative to the number of samples ($n$).
Performance and Applications
A common, naive approach to handling massive datasets is random subsampling (e.g., keeping only 1% of the points). However, Stream-SW proves significantly more accurate for the same memory budget because the quantile sketch intelligently "remembers" the shape of the distribution.
The researchers evaluated Stream-SW across diverse domains, yielding impressive results:
- Memory Efficiency: In tests with 2 million data points, standard SW crashed due to GPU "out of memory" errors. Stream-SW processed the exact same data effortlessly while maintaining a stable memory footprint.
- High-Dimensional Accuracy: On the 784-dimensional MNIST dataset, Stream-SW achieved approximation errors an order of magnitude lower than random subsampling (e.g., 0.0003 versus 0.003).
- Point Cloud Classification: In streaming 3D point cloud classification using ModelNet10, Stream-SW outperformed subsampled SW by 10-20% in accuracy under highly constrained memory conditions.
- Real-Time Detection: Using the MSRC-12 Kinect Gesture Dataset, Stream-SW detected transitions between human actions (such as switching from bending to throwing) much faster and more accurately than traditional sliding-window baselines.
Limitations and Future Work
While the theoretical foundation of Stream-SW is robust, the current implementation is written in pure Python. The authors note that there is substantial room for engineering speedups through optimized C++ libraries or parallelization.
Looking ahead, this streaming approach could be extended beyond the standard Sliced Wasserstein distance. Future research may adapt these techniques for Generalized Sliced Wasserstein or Spherical Sliced Wasserstein distances, opening the door to efficient, real-time analysis of complex, non-Euclidean data streams.
Summary updated