The set intersection problem is fundamental across multiple domains, yet its formal analysis has traditionally been approached under the comparison model. This paper studies the indexed-set intersection problem on the word RAM model, aiming to leverage the advanced features of modern processors to surpass the time bounds of comparison-based algorithms. Although implementing optimal comparisonmodel algorithms, such as Barbay and Kenyon’s, on top of word-RAM successor data structures yields immediate improvements, we question whether this model can be exploited even further. Let \(\mathcal{S} = \{ S_1, \ldots, S_N \}\) be a family of N integer sets, with \(S_i\ \subseteq\ [0, 2^w)\) (\(w\) being the number of bits in a word-RAM machine word) and \(|S_i|\ =\ n_i\). On this family, we want to answer query instances \(Q = \{i_1, \ldots , i_k\} \subseteq [1,N]\), asking to compute Int\((Q) = \cap_{i \in Q} S_i\). For any \(S_i\), and for \(1 \le c \le \lceil w/ \lg \ w\rceil\), we define \(S^{(c)}_i\) as the set obtained by truncating each element of \(S_i\) to its \(w - c\, \lg\, w\) most significant bits, with \(|S^{(c)}_i | = n^{(c)}_i\). We propose a new approach that combines several key techniques such as range reduction (to transform the original instance into subproblems over smaller universes), trie certificates (to efficiently intersect the resulting range-reduced sets), and a novel data structure we call w-trees to represent sets on universes that can be intersected in constant time per set by a word RAM. We integrate these ideas into a technique we call recursive range reduction to prove that our approach is able to represent any \(S_i\) using \(\Theta(c \cdot n_i^{(1)})\) words of space. The intersection Int\((Q)\) can be computed in time \(O(\delta^{(c)} \sum_{i \in Q^{(c)}} \lg\lg \frac{n_i^{(c)}}{\delta^{(c)}} + k \sum_{j=1}^{c-1} |\) Int\((Q^{(j)})| + |\) Int\((Q)|)\), which in a pathological worst case is \(O(\delta \sum_{i \in Q} \lg\lg \frac{n_i}{\delta})\), the same time obtained by applying a particular successor data structure on Barbay and Kenyon’s algorithm. Here, \(Q^{(j)}\) denotes the intersection sub-instance \(\cap_{i \in Q}S_i^{(j)}\). We argue, with experimental support, that the practical performance of our approach is likely to be significantly better than that of existing alternatives.

We study the indexed set intersection problem. Given a family \(\mathcal {S}=\lbrace S_1,\ldots ,S_N\rbrace\) of sorted integer sets, preprocess \(\mathcal {S}\) to answer queries \(Q\subseteq [1{..}N]\) that ask to compute \(\bigcap _{i\in Q} S_i\) . 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 \(\mathrm{O}(\delta \sum _{i\in Q}\lg \bigl (\frac{n_i}{\delta }\bigr))\) , where \(|S_i| = n_i\) and \(\delta\) is the alternation measure of Q . We also introduce a stronger difficulty measure \(\xi \le \delta\) , called the run alternation measure, and design an algorithm whose running time adapts to \(\xi\) , achieving \(\mathrm{O}(\xi \sum _{i\in Q}\lg \bigl (\frac{n_i}{\xi }\bigr))\) time on a pointer machine. On a transdichotomous word-RAM with word size w , we show that these algorithms can be implemented with a \(\Theta (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.