Abstract
Optimal Transport (OT) is a fundamental framework for comparing data distributions, yet its application in dynamic environments—where data points or weights are frequently updated—remains computationally prohibitive. Traditional static algorithms often require full re-computation, scaling quadratically with the number of nodes. This paper introduces the 2D Skip Orthogonal List, a specialized data structure designed to facilitate incremental updates via the Network Simplex algorithm. By leveraging the Euler Tour Technique and hierarchical range queries, the proposed method reduces update complexity to expected linear time ($O(|V|)$), delivering speedups of up to 1000x over static methods and 10x over entropic regularization techniques like Sinkhorn.
Introduction
Optimal Transport (OT) calculates the most efficient plan to transform one distribution into another. While widely adopted in machine learning and image processing, standard OT solvers are primarily static. In real-world scenarios such as time-series tracking or medical imaging, data is often dynamic: a single point may move, or a weight may shift. Re-computing the entire OT plan for every minor change is inefficient, typically requiring $O(|V|^2)$ time.
The authors address this by framing dynamic OT as a "patching" problem. Instead of starting from scratch, they utilize the Network Simplex algorithm to pivot an existing solution toward a new optimum. The challenge lies in the pivot step, which traditionally requires scanning all possible edges to find the best variable to update.
Methods: The 2D Skip Orthogonal List
The core innovation of this work is the integration of classic optimization theory with a novel hierarchical data structure. The transport plan, which forms a tree structure, is first represented as a linear sequence using the Euler Tour Technique. To handle the two-dimensional nature of the transport matrix, the authors extend this into a 2D representation.
To optimize the search for pivot variables, the authors wrap this sequence in a 2D Skip Orthogonal List. This structure is a multi-dimensional, hierarchical version of a skip list that supports "lazy propagation." This allows the algorithm to perform range updates and identify the minimum cost variable in expected $O(|V|)$ time, effectively bypassing the quadratic bottleneck of standard edge scanning.
Key Insights and Implementation
The efficiency of the algorithm stems from exploiting locality. Dynamic modifications usually only create small cycles of inefficiency within the transport plan. By using a 2D skip list, the authors define a "domination" relationship where high-level nodes represent the minimum values for entire blocks of the cost matrix.
This structured search mechanism transforms the pivot selection from a brute-force $O(|V|^2)$ scan into a guided $O(|V|)$ search. This transition from quadratic to linear complexity per update step is the primary driver of the observed performance gains.
Experimental Evaluation
The researchers evaluated the 2D Skip Orthogonal List on both synthetic Gaussian mixtures in high-dimensional space ($\mathbb{R}^{784}$) and the MNIST handwritten digit dataset.
Key Results: * Massive Speedups: For dynamic scenarios involving 40,000 nodes, the algorithm is approximately 1000x faster than the standard static Network Simplex algorithm. * Competitive Performance: It outperforms the popular Sinkhorn algorithm—often favored for its speed—by a factor of 10x in dynamic contexts. * Scalability: The performance remains stable and close to linear time as the number of nodes increases, demonstrating robust scalability.
Limitations and Future Work
Despite its speed, the 2D Skip Orthogonal List has trade-offs:
- Memory Footprint: The hierarchical pointer system can require up to $O(n^2)$ space in the worst case, potentially limiting its use on extremely large datasets.
- Cache Efficiency: The reliance on linked lists and pointers results in poor cache locality. Modern hardware performs better with contiguous array storage, whereas pointer-chasing can introduce latency.
Future research will focus on developing "memory-friendly" variants of these structures that maintain theoretical linear complexity while optimizing for RAM usage and modern CPU cache architectures.
Conclusion
By rethinking the data structures underlying the Network Simplex algorithm, the authors have provided a viable path for real-time, dynamic Optimal Transport. The 2D Skip Orthogonal List represents a significant step toward making OT practical for high-frequency, incremental data applications.
Summary updated