EUVIMEDEUVIMED entdecken
Crossref

Prune Early, Intersect Fast: PRISM, a Prefix-Based Radix Integer Set with Morphing Nodes

Adrian Riedl, Thomas Neumann

Proceedings of the VLDB Endowment · 01.09.2026 · 20 (1) · 53-65

DOI: 10.14778/3845598.3845603 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 06.11.2026. Verfasst von Adrian Riedl und 1 weiteren Autor:innen. Die Arbeit nennt 32 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Intersecting sets of integers is a fundamental operation in search engines and graph analytics. Yet most approaches treat integers as opaque values and compare them one by one, ignoring that every integer set partitions the key space into occupied and empty ranges. PRISM exploits this: it decomposes 64-bit integers into fixed-width prefix segments organized in a trie, where each node uses a bitmap to record which sub-ranges are occupied. Ranges absent from at least one operand are pruned without examining individual elements, fixed-width leaf segments map directly onto SIMD registers, and the structure extends naturally to k -way intersection via simultaneous descent. Morphing-node layouts adjust each node's size by occupancy, reducing memory usage by up to 8× on sparse data while minimally affecting throughput on dense data. We also evaluate PRISM on three real-world case studies: the Star Schema Benchmark, a TPC-H trigram index, and inverted list intersection on ClueWeb09. On all three, PRISM is the fastest method for intersection-heavy workloads, ahead of compressed-bitmap methods and more than an order of magnitude faster than general-purpose ordered and hash-based containers.

Zitieren

APA

Riedl, A., & Neumann, T. (2026). Prune Early, Intersect Fast: PRISM, a Prefix-Based Radix Integer Set with Morphing Nodes. Proceedings of the VLDB Endowment, 20(1), 53-65. https://doi.org/10.14778/3845598.3845603

Vancouver

Riedl A, Neumann T. Prune Early, Intersect Fast: PRISM, a Prefix-Based Radix Integer Set with Morphing Nodes. Proceedings of the VLDB Endowment. 2026;20(1):53-65. doi:10.14778/3845598.3845603

BibTeX
@article{Riedl2026,
  author = {Riedl, Adrian and Neumann, Thomas},
  title = {Prune Early, Intersect Fast: PRISM, a Prefix-Based Radix Integer Set with Morphing Nodes},
  journal = {Proceedings of the VLDB Endowment},
  year = {2026},
  volume = {20},
  number = {1},
  pages = {53--65},
  doi = {10.14778/3845598.3845603}
}
Kostenlos starten →