We study the indexed set intersection problem. Given a family \ (S= S₁, , SN \) of sorted integer sets, preprocess \ (S \) to answer queries Q ⊆1. . N that ask to compute \ (₈ ₐ Sᵢ \). We introduce trie certificates, a new approach for the adaptive analysis of set intersection algorithms. Trie certificates capture the difficulty of an instance and allow one to obtain adaptive bounds for the set intersection problem across multiple computational models. Using trie certificates, we revisit Trabb-Pardo’s algorithm Trabb-Pardo, 1978 in the pointer-machine model and prove an adaptive worst-case bound that matches the optimal comparison-model adaptive bound of Barbay and Kenyon Barbay and Kenyon, 2008, namely \ (O (₈ ₐ (nᵢ{) }) \), where | S i | = n i and δ is the alternation measure of Q. We also introduce a stronger difficulty measure ξ ≤ δ, called the run alternation measure, and design an algorithm whose running time adapts to ξ, achieving \ (O (₈ ₐ (nᵢ{) ) } \) time on a pointer machine. On a transdichotomous word-RAM with word size w, we show that these algorithms can be implemented with a Θ (w) -factor reduction in space, while retaining the above running times. Also on a transdichotomous word-RAM, via a decomposition of the original intersection instance into smaller subinstances, we show that the running time can be further improved. We then extend trie certificates to the thread-parallel setting by also decomposing each query into independent subinstances over disjoint subuniverses. We obtain a running-time bound that is determined by the hardest subinstance, and highlight the challenge of balancing difficulty across threads. Our experimental results empirically support our main findings, showing that our algorithms are competitive in practice and provide attractive space–time trade-offs.
Arroyuelo et al. (Tue,) studied this question.