Adaptive Set Intersection on the Word RAM

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.