Prune Early, Intersect Fast: PRISM, a Prefix-based Radix Integer Set with Morphing Nodes
PRISM is an integer set structure that splits 64-bit keys into prefix segments in a trie with bitmap nodes, pruning whole key ranges during intersection and mapping leaves onto SIMD registers for fast k-way intersection.
Paper (from PDF)
Read full textPrune Early, Intersect Fast: PRISM, a Prefix-based Radix Integer
Set with Morphing Nodes AdrianRiedl ThomasNeumann TUM TUM Munich,Germany Munich,Germany adrian.riedl@in.tum.de neumann@in.tum.de ABSTRACT Prefix-basedpruningforsetintersection Intersectingsetsofintegersisafundamentaloperationinsearch Case1:Sameprefix Case2:Differentprefix enginesandgraphanalytics.Yetmostapproachestreatintegers Intersectcommonchildren Prunetrees asopaquevaluesandcomparethemonebyone,ignoringthatev- eryintegersetpartitionsthekeyspaceintooccupiedandempty prefix: ∩ prefix: prefix: ∩ prefix: ------------- -------- ------------------- ------ ------------- --- --------- ------- ------- --------- ranges. PRISM exploits this: it decomposes 64-bit integers into 0 0 1 2 fixed-widthprefixsegmentsorganizedinatrie,whereeachnode usesabitmaptorecordwhichsub-rangesareoccupied.Ranges ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ --- --- --- --- --- --- --- --- --- --- absentfromatleastoneoperandareprunedwithoutexamining AND 1≠2 --- --- --- --- --- --- --- --- --- --- individualelements,fixed-widthleafsegmentsmapdirectlyonto SIMDregisters,andthestructureextendsnaturallyto𝑘-wayinter- prefixmismatch …
Explained
What happened
PRISM (Adrian Riedl and Thomas Neumann, TUM; PVLDB 2026) is a data structure for sets of 64-bit integers built to make set intersection fast. Intersection is the core operation behind search engines (intersecting posting lists) and graph analytics (common neighbours).
On three real workloads (Star Schema Benchmark filters, a TPC-H trigram index, inverted lists on ClueWeb09), PRISM is the fastest on intersection-heavy work, ahead of compressed bitmaps like Roaring, and more than 10x faster than general-purpose sorted or hash containers. Its "morphing" nodes use up to 8x less memory on sparse data.
Why it works
Most set structures treat integers as opaque values and compare them one by one (merge of sorted arrays, hash probing). But every set splits the key space into occupied and empty ranges, and you can skip a whole empty range at once.
PRISM:
- Splits each 64-bit integer into fixed-width segments (like a radix trie). Numbers sharing a prefix share a path.
- Each node stores a bitmap of which children exist, not a list.
- To intersect two sets, walk both tries top-down together:
- Same prefix: a single bitwise
ANDof the two bitmaps gives the shared children. Descend only into those. - Different prefix: the whole subtree is pruned without looking at its elements.
- Same prefix: a single bitwise
- Leaves are fixed-width bitmaps sized to SIMD registers, so the last step is a vectorized
AND. - Prefix compression collapses one-child chains, and node size adapts to occupancy ("morphing"), which saves memory on sparse data.
It extends to k-way intersection by descending all tries at once.
The bigger pattern
Make structure reveal emptiness. The fastest work is the work you prune before touching data, the same idea as zone maps and min/max indexes in column stores, or bloom filters. It also shows how hardware-shaped layouts (bitmaps matching SIMD width) beat clever algorithms on generic containers.
What it means in practice
- If you intersect ID sets in hot paths (tag filters, "users who did A and B", feed eligibility), the representation matters more than the algorithm. Roaring bitmaps (available in Redis modules, Postgres extensions and most languages) are a solid default today.
- Postgres uses a similar idea internally in BitmapAnd for combining indexes. Seeing it in
EXPLAINmeans the planner is intersecting row sets. - For recommendation or video catalogue systems, fast set intersection is a building block for candidate filtering at scale.