Tight Asymptotic Bounds on the Size of Order Graphs
cs.DS
Submitted: 2026-10-29
Updated: 2026-11-07
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
The gist: Order graphs were introduced by Arroyuelo et al.
Abstract
Order graphs were introduced by Arroyuelo et al. (TODS 2024) as a generalization of the ring index, to support worst-case optimal joins on relations of arity d while storing few columns: the index stores one column per edge, so its size is proportional to the number of edges of an order graph. It was known that the minimum number of edges lies between Ω(2 d sqrt d) and O(2 d d), and the lower bound had been claimed to be 42 for d=6. We first exhibit an optimal order graph with only 40 edges for d=6, and show that the proof of that lower bound holds only for unions of cycles, whereas order graphs can be smaller than the smallest set of cycles. We give a corrected statement and proof that holds for every order graph: there must be at least m dm m/2 edges. This bound is 40 (hence tight) for d=6. We then settle the asymptotic question: the minimum size is Θ(2 d sqrt d). This is obtained via an explicit construction, based on symmetric chain decompositions of the Boolean lattice, with at most (d-1) d/2 +2 d edges. The upper bound is within a factor 4+O(d-1/2) of the lower bound, and both numerically and asymptotically better than trie switching. Finally, we cast the problem as a set cover with connectivity constraints, which yields an exact ILP formulation and a greedy heuristic. With them we find optimal order graphs for d at most 6 in the bidirectional and for d at most 7 in the unidirectional model, showing that our lower bounds are tight there, and improve the best known order graphs for d=7 and 8.
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time