EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Adaptive Set Intersection via Trie Partition Certificates

Diego Arroyuelo, Juan Pablo Castillo, José M. Cazorla

ACM Transactions on Database Systems · 31.12.2026 · 51 (4) · 1-55

DOI: 10.1145/3812648 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Database Systems, online erschienen am 15.06.2026. Verfasst von Diego Arroyuelo und 2 weiteren Autor:innen. Die Arbeit nennt 89 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: ANID—Millennium Science Initiative Program—Code ICN17_002, ANID Ph. D. Scholarship program.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • ANID—Millennium Science Initiative Program—Code ICN17_002
  • ANID Ph. D. Scholarship program

Zitieren

APA

Arroyuelo, D., Castillo, J. P., & Cazorla, J. M. (2026). Adaptive Set Intersection via Trie Partition Certificates. ACM Transactions on Database Systems, 51(4), 1-55. https://doi.org/10.1145/3812648

Vancouver

Arroyuelo D, Castillo JP, Cazorla JM. Adaptive Set Intersection via Trie Partition Certificates. ACM Transactions on Database Systems. 2026;51(4):1-55. doi:10.1145/3812648

BibTeX
@article{Arroyuelo2026,
  author = {Arroyuelo, Diego and Castillo, Juan Pablo and Cazorla, José M.},
  title = {Adaptive Set Intersection via Trie Partition Certificates},
  journal = {ACM Transactions on Database Systems},
  year = {2026},
  volume = {51},
  number = {4},
  pages = {1--55},
  doi = {10.1145/3812648}
}
Kostenlos starten →