← Back to summary
Prune Early, Intersect Fast: PRISM, a Prefix-based Radix Integer Set with Morphing Nodes
Converted from PDF with markitdown. Layout may be rough.
Prune 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
| sectionviasimultaneousdescent. | | Morphing-nodelayoutsadjust | | | | | | | |
| ------------------------------ | --- | -------------------------- | --- | --- | --- | --- | --- | --- | --- |
eachnode’ssizebyoccupancy,reducingmemoryusagebyupto
| | | | | | | intersect | pruned | pruned | |
| --- | --- | --- | --- | --- | --- | --------- | ------ | ------ | --- |
8×onsparsedatawhileminimallyaffectingthroughputondense
| data. We | also evaluate PRISM | on three | real-world | case studies: | | | | | |
| -------- | ------------------- | -------- | ---------- | ------------- | --- | --- | --- | --- | --- |
theStarSchemaBenchmark,aTPC-Htrigramindex,andinverted Figure1:PRISMorganizesintegersetsinatrieoverfixed-
listintersectiononClueWeb09.Onallthree,PRISMisthefastest widthprefixsegments,whereeachnodestoresaprefixanda
methodforintersection-heavyworkloads,aheadofcompressed- bitmaprecordingwhichchildsubtreesarepresent.Intersec-
tiontraversesbothtriestop-down:wheretwonodesshare
bitmapmethodsandmorethananorderofmagnitudefasterthan
aprefix,itdescendsintotheircommonchildren;wherethe
general-purposeorderedandhash-basedcontainers.
prefixesdiffer,itprunestheentiresubtreewithoutinspect-
ingitselements.
PVLDBReferenceFormat:
AdrianRiedlandThomasNeumann.PruneEarly,IntersectFast:PRISM,a
Prefix-basedRadixIntegerSetwithMorphingNodes.PVLDB,20(1):53-65,
compressedbitmaprepresentationssuchasEWAH[21]andRoar-
2026.
ing[9,22]havebeenproposed,offeringfavorablecompression
doi:10.14778/3845598.3845603
ratiosandefficientbitwiseoperations.However,thesestructuresin-
curoverheadfromrun-lengthdecodingorcontainer-typedispatch
PVLDBArtifactAvailability:
duringintersection,andtheirperformancedegradesonskewed
Thesourcecode,data,and/orotherartifactshavebeenmadeavailableat
https://gitlab.db.in.tum.de/AdrianRiedl/intersection-vldb27. workloadsthatfrequentlyariseinpractice.
Theseapproachestreateachelementasanopaquekey,sotheir
1 INTRODUCTION representations reveal nothing about which regions of the key
| | | | | | space | a set occupies. | Yet every | set partitions | the key space the |
| ------------------------ | --- | ------------------------------- | --- | --- | ----- | --------------- | --------- | -------------- | ----------------- |
| Setintersectionisacommon | | primitiveininformationretrieval | | | | | | | |
sameway,regardlessofhowidentifiersareassigned.Someranges
andgraphprocessing:searchenginesintersectpostingliststore-
holdelementsandothersholdnone.Arepresentationthatrecords
solvequeries,andgraphanalyticscomputecommonneighborsfor
occupancyperprefix-definedsubtreecanthereforedecideawhole
trianglecountingandlinkprediction.
subtreeatonce.Intersectionprunesasubtreethatisabsentfrom
Givenitsimportance,researchershavestudiedsetintersection
anyoperand,andunion,difference,andsymmetricdifferencecopy
extensively.Classicalapproaches,e.g.merge-basedintersectionof
ordiscardasubtreethatbelongstooneoperandalone,without
sortedarrays[3–6,12,16]andhash-basedprobing[13],remain
descendingintoit.Sortedarrayscompareacrossdisjointranges
widelydeployedfortheirpredictableperformance.Morerecently,
instead.Hashsetsdiscardthestructurethatwouldrevealthose
| | | | | | ranges, | and compressed | bitmaps | often traverse | containers that |
| --- | --- | --- | --- | --- | ------- | -------------- | ------- | -------------- | --------------- |
ThisworkislicensedundertheCreativeCommonsBY-NC-ND4.0International contributenothingtotheresult.Allthreerevisitindividualelements
License.Visithttps://creativecommons.org/licenses/by-nc-nd/4.0/toviewacopyof thatacoarser,subtree-levelviewwouldletthemskip.Wetherefore
thislicense.Foranyusebeyondthosecoveredbythislicense,obtainpermissionby
emailinginfo@vldb.org.Copyrightisheldbytheowner/author(s).Publicationrights proposeastructurethatrecordswhichprefix-definedsubtreesof
licensedtotheVLDBEndowment. anintegersetarepresentandwhichareabsent.Setoperationsthen
ProceedingsoftheVLDBEndowment,Vol.20,No.1ISSN2150-8097.
becomeacoordinatedtraversalthatresolveswholesubtreesbefore
doi:10.14778/3845598.3845603
examiningindividualelements.
53
𝜆=0 0 𝜆=0 𝐵=10···0 p=0x0,𝜆=1
0 𝐵=110···0
𝜆=1 0 1 𝜆=1 𝐵=110···0 0 1
0 1 p=0x00,𝜆=2 p=0x0123,𝜆=4
𝜆=2 0 1 2 𝜆=2 𝐵=110···0 𝐵=0010···0 𝐵=110···0 𝐵=000010···0
0 1 2 0 1 𝑃01[4]=0000010···0
𝜆=3 0 0 3 𝜆=3 𝐵=10···0 𝐵=10···0 𝐵=00010···0 p=0x0000,𝜆=4 p=0x0010,𝜆=4
0 0 3 𝐵=10···0 𝐵=10···0
𝜆=4 0 0 4 𝜆=4 𝐵=10···0 𝐵=10···0 𝐵=000010···0 𝑃01[0]=10···0 𝑃01[0]=010···0
𝜆=5 𝑃01[0]=10···0 𝑃01[0]=010···0 𝑃01[4]=0000010···0
𝜆=5 0 1 5
(a)Naïvetrie (b)Bitmapnodes,foldedleaves (c)PRISM
Figure2: FromanaïvetrietoPRISMonthree24-bitkeys(0x000000,0x001001,0x012345;𝑏=4,ℓ=6).(a)Onenodepersegment.
(b)Eachnodestoresapresencebitmap𝐵insteadofachildlist,andthelasttwosegmentsfoldintoasingleleaf(𝐵for𝜆=4,𝑃01
for𝜆=5).(c)Prefixcompressioncollapsesone-childchainsintoonenodetaggedwithprefix𝑝anddivergencelevel𝜆.
Inthispaper,wepresentPRISM,anintegersetstructurethatre- ART[19],andmemoryconsumptiondropsbyupto8×on
alizesthisidea.PRISMdecomposes64-bitintegersintofixed-width sparsedata(Sections4and5.2.1).
segmentsorganizedinatriewhoseinternalnodesencodechild (4) WeevaluatePRISMonsyntheticdataagainststrongbase-
presenceviabitmaps.Intersectionthenreducestoasynchronized linesfromeverymajoralgorithmiccategory(merge-based,
top-downtraversalinwhichasinglebitwiseANDoftwobitmaps hierarchical,hash-based,andcompressedbitmaps),show-
ateachlevelidentifiesthesharedchildrenandprunesalldisjoint ingitiscompetitiveacrossdistributionsandoverlapcoeffi-
branchesfromfurtherconsideration.Figure1illustratesthetwo cientsandthebestperformerinmanycases(Section5).
characteristiccases:whentwonodesshareaprefix,intersection (5) Westudythreereal-worldcases:queryfiltersontheStar
descendsintotheircommonchildrenandprunestherest;whenthe Schema Benchmark, a TPC-H trigram index, and an in-
prefixesdiffer,theentirebranchispruned,yieldinganemptyresult. vertedindexonClueWeb09,wherePRISMisthefastest
Becauseeachnodecoversacontiguoussubsetofthekeyspace,a methodontheintersection-heavyworkloads(Section6).
singleprefixmismatchatanylevelsufficestoskiptheentiresub-
treebeneathit.Attheleaves,thefixed-widthlayoutofthepayload
2 APREFIX-BASEDRADIXINTEGERSET
bitmapsalignswithSIMDregisterwidths,sothefinalsegmentof
theintersectionexecutesasablockofvectorizedbitwiseoperations. Traditionalsetimplementationssuchashashsets,balancedtrees,
Thesametraversalpatternextendsto𝑘inputsbyreplacingthepair- andsortedarrayscompareelementspairwise,requiringworkpro-
wiseANDwitha𝑘-aryconjunction,identifyingcommonchildren portional to the cardinality of the operands regardless of value
inonepassandavoidingtheintermediatematerializationinherent distribution.Bytreatingintegersasopaquekeys,theseapproaches
inrepeatedbinaryintersection.Toaccommodateworkloadswith failtoexploitthefactthatsubsetsofvaluesmayshareordifferin
highlyvariabledensity,PRISMfurthersupportsmorphing-nodelay- entireprefixes.
outsthatsizeeachnodetoitsactualoccupancy,reducingmemory PRISMaddressesthislimitationbydecomposingeachinteger
consumptiononsparseinputswithminorimpactondensethrough- intofixed-widthsegmentsandinsertingitintoaprefixtriewhose
put.Beyondintersection,thesametriestructuresupportsunion nodesencodechildoccupancyasbitmaps.Eachnoderepresentsa
andothersetoperationsthroughanalogoustop-downtraversals. contiguousrangeofvaluesthatshareacommonprefix,reducingset
Wemakethefollowingcontributions: operationstosynchronizedtraversalswithbitwiseoperationsatev-
erylevel.Intersectionprunesentiresubtreeswhenbitmapsindicate
disjointranges,whileunion,difference,andsymmetricdifference
(1) WeintroducePRISM,atrie-basedintegersetthatencodes copysubtreesexclusivetooneoperandwithoutdescendinginto
per-nodechildoccupancyasbitmapsandusesadaptive them.Concretely,PRISMcombinesthefollowingfourprinciples:
prefixcompressiontoreducesetoperationstosynchronized 1.Bit-LevelPartitioning.Each𝑛-bitintegerissplitintoℓ=⌈𝑛/𝑏⌉
bitwisetraversals(Section2). segmentsof𝑏bits,consumedfrommosttoleastsignificantalong
(2) Wepresentaunifiedset-operationframeworkforPRISM, anyroot-to-leafpath.If𝑛isnotamultipleof𝑏,therootsegment
includinga𝑘-wayintersectionwithnointermediatema- (𝜆=0)carriestheremaining𝑛mod𝑏bits;allothersegmentsare
terializationthatprunesentiresubtreesbyexploitingthe exactly𝑏bitswide.Figure2ashowsanaïvetriestoringthree24-bit
trie’shierarchicalstructure(Section3). valuesacrosssix4-bitsegments.
(3) Wereusethebitmapinoursetrepresentationasauniform 2.BitmapEncoding.Tolocateoccupiedchildreninconstanttime
nodeinterface,sothatasinglesetofSIMDroutinescan andreducesetoperationstobitwiseprimitives,PRISMmaintainsa
operateonallnodesizeswithoutthetraversallogicdis- presencebitmap𝐵of2𝑏bitspernode,where𝐵[𝑖]=1ifandonly
patchingonnodetype.Nodesizesfollowoccupancy,asin ifthesubtreecontainsavaluewhosesegmentatthecurrentlevel
54
equals𝑖.Anaïvetrienode,incontrast,eitherliststheoccupied Indenseregions,leafbitmapsencodeupto2𝑏 valuesin2𝑏 bits,
segmentvaluesexplicitlyormarkseachchildslotindividually,both whichis𝑂(1)spacepervalue.
ofwhichrequireascantolocateoccupiedchildren.InFigure2b, ParameterSelection.Ourexamplesuse𝑏=4forclarity,butthe
𝐵=10⋯0attherootindicatesthatthesegmentvalue0isoccupied. implementationuses𝑏 = 6forhardwareefficiency.With𝑏 = 6,
3.LeafFolding.Toeliminateawastefulpointerindirectionat boththepresencebitmap𝐵andthepayloadarray𝑃contain26=64
thedeepestlevel,PRISMfoldsthefinallevelintoitsparent:each entries.Thepresencebitmapfitsexactlyinasingle64-bitword,so
occupiedslotatlevel𝜆=ℓ−2storesa2𝑏-bitbitmapencodingthe bitwiseoperationsandhardwareinstructionssuchaspopulation
presentvaluesofsegmentℓ−1inplaceofachildpointer.Anaïve count(POPCNT)andbitscanning(BSF/BSR)applydirectly.Both
trie,incontrast,encodesthefinalsegmentvaluesindedicatedleaf payloadarraysoccupy64entries,sotheyhaveidenticalmemory
nodesatlevel𝜆 = ℓ−1(cf.Figure2a);adirectbitmapencoding layouts and cache line footprints. Internal nodes store 64 child
wouldreplacethesewith2𝑏-bitbitmapsreachedthroughpointers pointers,andleafnodesstore64bitmapsinthesamespace,making
fromlevel𝜆=ℓ−2,payingonepointerdereferenceforapayload transitionsbetweenthetwonoderepresentationsuniform.AVX-
nolargerthanthepointeritself.Forexample,therightmostleaf 512SIMDinstructionsprocesseight64-bitvaluesatonce,soleaf-
inFigure2bencodesthevalue0x012345via𝐵[4] = 1at𝜆 = 4 levelbitmapscanbeoperatedoninvectorizedform.Thestructure
togetherwithbit5setinthebitmapstoredat𝑃01[4]. parametersthereforematchthehardware:64-bitwords,64-byte
4. Adaptive Prefix Compression. To avoid wasting space on cachelines,andSIMDregisterwidths.For64-bitintegers,𝑏 = 6
chainsofone-childnodes,PRISMallowsnodestospanmultiple givesℓ = ⌈64/6⌉ = 11segments,soaroot-to-leafpathvisitsat
segmentsbyaddingaprefix𝑝andalevel𝜆toeachnode:𝑝records mostℓ−1=10nodes.
thebitpatternsharedbyallvaluesinthesubtree,and𝜆identifies
thefirstsegmentatwhichthosevaluesdiverge.Aninsertionthat 3 SETOPERATIONS
introducesanewdivergencesplitsthepathbycreatinganinternal PRISMencodessubsetinformationhierarchically,andsetopera-
nodeatthedivergencepoint.Thispreservestheinvariantthatevery tionsusethatstructuretodecidewhichsubtreescancontributeto
internalnodehasatleasttwooccupiedchildren,boundingboth theresult.Intersectiondirectlydiscardssubtreeswithnoshared
treedepthandmemoryfootprint.Afixed-depthtrieofℓ−1levels, prefix.Union,difference,andsymmetricdifferencehandleasubtree
incontrast,wastesspacewheneveraninternalnodehasasingle thatbelongstoonlyoneoperandwithoutinspectingitsindividual
occupiedchild,sincethecorrespondingpathdegeneratesintoa elements.Wetraversetheinputtriessynchronously,identifycom-
chainofone-childnodes.AsshowninFigure2c,thefirsttwonodes monprefixesandsharedsubtreesateachlevel,andprunelarge
ofthenaïvetriecollapseintoasinglenodewithprefix0x0andlevel portionsofthesearchspacewithoutexaminingelementsdirectly.
𝜆=1,sinceallvaluessharethetopsegment.Itsrightchildfurther Thisgivessubstantialspeedupsovergenericset-operationalgo-
collapsestoasinglenodewithprefix0x0123at𝜆=4,becausethe rithms,whichhavenosuchstructuralinformation.
thirdvaluehasnosiblingthatsharesanysubsequentsegment.
Node Representation. Each node 𝑣 represents a subset of the 3.1 𝑘-WaySetIntersection
storedsetthroughfourcomponents:
Intersectingmultiplesetsarisesnaturallyindatabaseworkloads,
Prefix𝑝 isthelongestsegment-alignedbitpatternsharedbyall forinstancewhenevaluatingconjunctivefilterpredicatesorprob-
valuesin𝑣’ssubtree. ingtrigramindexeswhereeachtrigramproducesacandidateset.A
Level𝜆∈{0,…,ℓ−2} isthesegmentatwhichthevaluesinthe naïveapproachappliesbinaryintersectionrepeatedly,((𝑆 ∩𝑆 )∩
1 2
subsetbegintodiverge;equivalently,𝑝spansthefirst𝜆segments. 𝑆 )∩⋯,materializing𝑂(𝑘)intermediatestructuresandrequiring
3
Presencebitmap𝐵 is a 2𝑏-bit vector recording occupancy at 𝑂(𝑘)separatetreetraversals.Worse,onecanconstructcasesin
level𝜆,with𝐵[𝑖]=1ifandonlyifsegmentvalue𝑖isoccupied. whichanyorderingofbinaryintersectionyieldsnon-emptyinter-
Payload𝑃 holdsupto2𝑏entriesalignedwith𝐵,definedwher- mediateresultsevenwhenthefinalintersectionisempty[28].The
ever𝐵[𝑖]=1.Theformof𝑃[𝑖]dependsonthenodetype: bitmap-basednoderepresentationofPRISMavoidsbothproblems
Internal (𝜆 < ℓ−2): 𝑃[𝑖] = 𝑃→[𝑖] is a pointer to the child byallowingintersectiontoproceedrecursivelyfromtherootover
responsibleforsegmentvalue𝑖. all𝑘inputssimultaneously:ateachlevel,asingle𝑘-arybitwise
Leaf (𝜆=ℓ−2):𝑃[𝑖]=𝑃01[𝑖]isa2𝑏-bitbitmapencodingthe conjunctionacrossallnodebitmapsidentifiesexactlythechildren
valuesofthefinalsegmentℓ−1presentinthesubtree. sharedbyeveryoperand,restrictingsubsequenttraversaltocom-
monsubtreesandpruningeverybranchabsentfromanyoperand
SpaceComplexity.Foraset𝑆ofcardinality𝑁,thespaceis𝑂(𝑁):
withoutfurtherinspection.Recursionterminatesattheleaflevel,
adaptive compression keeps at least two occupied children per
andresultnodesareassembledbottom-up,yieldingtheoutputset
internalnode,sothetrieholdsfewerthan𝑁internalnodes,each
withoutintermediatematerialization(Listing1).
ofconstantsize.Withoutit,theboundwouldbe𝑂(𝑁 ⋅ℓ),since
avaluecouldrequireonenodeperlevel.Theactualspacefalls 3.1.1 Algorithm Description. Given 𝑘 input sets {𝑆 ,⋯,𝑆 }, de-
1 𝑘
belowthisboundbyanamountthatdependsonhowthevaluesare scribedbytheirroots{𝑣 ,⋯,𝑣 },PRISMintersectsthembytravers-
1 𝑘
distributed.Clusteredvaluessharelongprefixes,somultiplelevels ingall𝑘structuresjointly,combiningprefix-basedpruningtoskip
collapseintosinglenodesandbothtreedepthandnodecountdrop. entiresubtreesirrelevanttotheresult,level-misalignmenthandling,
Uniformlydistributedvaluesgiveabalancedtreeinwhicheach andlevel-wiseintersection(cf.Listing1).
pathspansmultiplelevels,sodegeneratelinearchainsdonotoccur. 1 Prefix-Based Pruning. Since each node covers only the
subsetofvaluessharingacommonprefix,nodeswhoseprefixes
55
function INTERSECT(𝑣 , , ⋯, ) bitwiseconjunctionofallnodebitmaps,
| 1 | | | | 1 𝑣 2 | 𝑣 𝑘 | | | | | | | | | | |
| --- | ------- | ------------ | --- | ------- | ------------ | --------- | -------- | --- | --- | --- | --- | ------ | ------ | --- | --- |
| | if ∃𝑖∶𝑣 | = null | // | Return | ∅ if | any input | is empty | | | | | | | | |
| 2 | | 𝑖 | | | | | | | | | | | 𝑘 | | |
| 3 | return | null | | | | | | | | | | | | | |
| | | | | | | | | | | | | 𝐵 | =⋀𝑣.𝐵, | | |
| 4 | 𝑀← | prefixMask(𝑣 | | .𝜆) ∧⋯∧ | prefixMask(𝑣 | | .𝜆) | 1 | | | | common | 𝑖 | | |
| | | | | 1 | | | 𝑘 | | | | | | 𝑖=1 | | |
5 𝑝←𝑣 1 .𝑝∧𝑀
| | for | each 𝑖 | in 2…𝑘 | do // | Prefix-Based | | Pruning | | | | | | | | |
| --- | --- | -------- | ------ | ----- | ------------ | --- | ------- | --- | ------------------------------------ | --- | --- | --- | --------- | --------------- | --- |
| 6 | | | | | | | | | andrecurseonlyonpositionsℬ={𝑗 | | | | ∣𝐵 common | [𝑗]=1},reducing | |
| 7 | if | (𝑣 .𝑝∧𝑀) | ≠𝑝 | | | | | | | | | | | | |
| | | 𝑖 | | | | | | | thebranchingfactorfromthemaximumof2𝑏 | | | | | downto|ℬ|.The | |
| 8 | | return | null | | | | | | | | | | | | |
intersectionthenproceedsdifferentlydependingonwhetherthe
| 9 | if ∃𝑖,𝑗∶𝑣 | .𝜆≠𝑣 | .𝜆 // | Level | Misalignment | | | | | | | | | | |
| --- | --------- | ------- | --------- | ----- | ------------ | --- | --- | --- | ---------------------------- | --- | --- | --- | --- | --- | --- |
| | | 𝑖 | 𝑗 | | | | | | | | | | | | |
| 10 | 𝑣 𝐷 | ←argmax | 𝑣𝑖 𝑣 𝑖 .𝜆 | | | 2 | | | nodesareinternalorleafnodes: | | | | | | |
11 for each 𝑣 𝑆 with 𝑣 𝑆 .𝜆<𝑣 𝐷 .𝜆 do 3.1 LeafNodeIntersection:Attheleaflevel,eachpayload
| | | 𝑣 ← descendInto(𝑣 | | , | 𝑣 ) | | | | | | | | | | |
| --- | ------ | ----------------- | ------- | ------------ | ------ | --- | --- | --- | --- | ------------------------------------------------ | ------------------- | --- | --- | --- | --- |
| 12 | | 𝑆 | | 𝑆 | 𝐷 | | | | | entryisabitmapoverthefinalsegment,sointersection | | | | | |
| 1 3 | | if 𝑣 = | nu l l | | | | | | | | | | | | |
| | | 𝑆 | | | | | | | | reducestoasingle𝑘-arybitwiseANDperposition𝑖∈ℬ: | | | | | |
| 1 4 | | r e tu rn | n u ll | | | | | | | | | | | | |
| 15 | return | INTERSECT(𝑣 | | , | ⋯, 𝑣 ) | | | | | | | | 𝑘 | | |
| | | | | 1 | 𝑘 | | | | | | | | | | |
| 16 | else | // Level-wise | | Intersection | | | | | | | 𝑁.𝑃01[𝑖]=⋀𝑣.𝑃01[𝑖]. | | | | |
| | 𝐵 | ← 𝑣 | .𝐵 ∧⋯∧𝑣 | .𝐵 | | | | | | | | | 𝑗 | | |
| 1 7 | comm | o n 1 | | 𝑘 | | | | 3 | | | | | | | |
| 1 8 | i f | 𝐵 | = 0 | | | | | | | | | | 𝑗=1 | | |
c om mon
19 return null Positionsthatyieldanemptybitmapcontributenovaluesto
20 𝑁← createNode(𝑣 .𝜆, 𝑝) theresult,sothepresencebitmapisupdatedas(cf.line24):
1
| 21 | if | isLeaf(𝑣 | 1 ) | | | | | | | | | | | | |
| --- | --- | ---------- | ----------- | ------------- | ------- | ------ | --- | --- | --- | --- | -------- | --- | ------------ | --- | --- |
| | | for each | set | bit 𝑖 | in 𝐵 | do 3.1 | | | | | | | if𝑁.𝑃01[𝑖]≠0 | | |
| 22 | | | | | common | | | | | | | 1 | | | |
| 2 3 | | 𝑁 . 𝑃 0 1 | [𝑖 ]← 𝑣 . 𝑃 | 0 1 [𝑖 ]∧ ⋯∧𝑣 | .𝑃01[𝑖] | | | | | | 𝑁.𝐵[𝑖]={ | | | | |
| | | | 1 | | 𝑘 | | | | | | | 0 | otherwise. | | |
| 2 4 | | 𝑁 . 𝐵[ 𝑖 ] | ← 𝑁 .𝑃 0 | 1 [ 𝑖] ≠ 0 | | | | | | | | | | | |
25 else
| | | | | | | | | 3.2 | | 3.2 I n t e rn | a lN o d e | In t e rs e | c t io n : F o ri | n t er n a l n o d e s , | e a c h p o - |
| --- | --- | -------- | -------- | ------- | ---------- | ------- | --- | --- | --- | -------------- | ---------- | ----------- | ----------------- | ------------------------ | ------------- |
| 2 6 | | fo r e a | c h se t | b i t 𝑖 | in 𝐵 co mm | o n d o | | | | | | | | | |
𝑁 .𝑃 → [ 𝑖] ← I NT E R SE CT (𝑣 .𝑃 → [ 𝑖 ], ⋯ , 𝑣 .𝑃→[𝑖]) s iti o n 𝑖 ∈ ℬ m a y pr o d u c e a n o n -e m p t y c h il d s u b t r e e , so t h e
| 2 7 | | | | | 1 | | 𝑘 | | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
28 𝑁.𝐵[𝑖]←𝑁.𝑃→[𝑖]≠ null procedurerecursesonthecorresponding𝑘-tupleofchil-
29 return 𝑁.𝐵=0 ? null : collapseIfSingleton(𝑁) dren.Aswithleafnodes,thepresencebitmapreflectsonly
Listing1:𝑘-wayintersectionalgorithmreturninganotherset positionswhoserecursivecallreturnedanon-emptyresult
(cf.line28):
| | | | | | | | | | | | | 1 if𝑁.𝑃→[𝑖]≠null | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | ---------------- | --- | --- | --- |
𝑁.𝐵[𝑖]={
| | | | | | | | | | | | | 0 otherwise. | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | ------------ | --- | --- | --- |
differmustrootdisjointsubtreesandcanbeprunedimmediately.To
testcompatibilityacrossall𝑘operands,wecomputethecombined Since PRISM requires every internal node to have at least two
alignmentmask children,thealgorithmrestoresthisinvariantbeforereturningby
pruningemptysubtreesandcollapsinganodeleftwithasingle
𝑘
child(collapseIfSingleton).Thiskeepstheresultcompactand
𝑀 ←⋀prefixMask(𝑣.𝜆),
𝑖
| | | | | 𝑖=1 | | | | | well-formed,improvingspaceefficiencyandqueryperformance | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | ------------------------------------------------------- | --- | --- | --- | --- | --- | --- |
forsubsequentoperations.
whereprefixMask(𝜆)producesthebitmaskcoveringthesegments
[0,𝜆).Thismaskretainsonlythebitsthatarepartoftheprefixin 3.1.2 IntersectionExample. Figure3illustratestheexecutiontrace
everynode,soifany(𝑣 .𝑝∧𝑀)differsfrom(𝑣 .𝑝∧𝑀),thesubtrees ofthealgorithmonthebinarycase(𝑘 = 2);thegeneral𝑘-way
| | | | 𝑖 | | | 1 | | | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
rootedat𝑣 1 ,…,𝑣 𝑘 aremutuallydisjointandrecursionterminates caseproceedsanalogouslywith𝑘simultaneousdescents.Theinput
immediately. comprisestwoPRISMindexes𝐿and𝑅,bothsharingtherootprefix
2 LevelMisalignment.Whentheoperandnodessharethe 0x1atlevel𝜆=1.First,thealgorithmexecutestheprefixmatching
sameprefixbutresideatdifferentlevels,thedeepernodescover check(1)andcomputes𝐵 =11,indicatingthatbothchild
common
subsetsoftheshallowerones,andwemustfirstalignthemtoa positionsrequirerecursiveprocessing(3)(cf.Figure3a).Based
| commonlevelbeforeintersecting.Let𝑣 | | | | | | =argmax | | 𝑣 .𝜆denote | | | | | | | |
| ---------------------------------- | --- | --- | --- | --- | --- | ------- | --- | ---------- | --- | --- | --- | --- | --- | --- | --- |
𝐷 𝑣 𝑖 onthisresult,thealgorithmthenexplorestwoparallelbranches
𝑖
thedeepest(mostspecific)node.Foreachshallower(lessspecific) correspondingtothesetbitsin𝐵 (3.2).
common
node𝑣 with𝑣 .𝜆 < 𝑣 .𝜆,werecursivelydescendintothatnode Forthefirstbranch(𝐵 [0]=1,cf.Figure3b),thealgorithm
| | 𝑆 | 𝑆 | 𝐷 | | | | | | | | | common | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | ------ | --- | --- | --- |
followingtheprefixbitsof𝑣 untilwereachatleast𝑣 ’slevel detectsalevelmisalignment:𝐿’schildresidesat𝜆 =4while𝑅’s
| | | | | 𝐷 | | | | 𝐷 | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
(descendInto).Ifthedescentreachesamissingentry,novalue childresidesat𝜆 = 2.Following 2,thealgorithmidentifiesthe
in𝑣 𝑆 ’ssubtreematches𝑣 𝐷 ’sprefix,andtheintersectionisempty. shallower node (𝜆 = 2) and descends to the appropriate child
Otherwisethedescentpathisunique,thoughprefixcompression determinedbythedeepernode’sprefix(𝜆=4),reachingthetarget
maycarryitpast𝑣 ’slevel;therecursivecallre-checksalignment nodeatthecommonlevel.Thesubsequentrecursivecalldetectsa
𝐷
anddescendsagainifneeded. prefixmismatchbetween0x1000and0x1001,triggeringimmediate
Level-wiseIntersection.Whenall𝑘nodessharecompati- subtreepruning(cf.Figure3d).
3
| | | | | | | | | | | Forthesecondbranch(𝐵 | | | [1]=1,cf.Figure3c),bothchil- | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | -------------------- | --- | --- | ---------------------------- | --- | --- |
bleprefixesandresideatthesamelevel,theirsubtreescoverthe common
samesubsetoftheuniverse,sotheirintersectionreducestoin- drenareleafnodesat𝜆=4withmatchingprefixes.Thealgorithm
dependentlyintersectingeach𝑘-tupleofcorrespondingchildren. appliesleaf-levelintersection(3.1),computingthebitwiseconjunc-
Toidentifywhichchildrenexistineverysubtree,wecomputethe tionofthepayloadbitmapstoproducethefinalresultinFigure3e.
56
3.2:𝐵c 𝜆 = 1 mon[0]=1
| | p=0x1,𝜆=1 | | ∩ | p=0x1,𝜆=1 | | o m | | p=0x1,𝜆=1 | | ∩ | p=0x1,𝜆=1 | |
| --- | --------- | --- | --- | --------- | --- | --- | --- | --------- | --- | --- | --------- | --- |
| | 𝐵=110···0 | | | 𝐵=110···0 | | | | 𝐵=110···0 | | | 𝐵=110···0 | |
| | 0 | 1 | | 0 | 1 | | | 0 | 1 | | 0 | 1 |
p=0x1000,𝜆=4 p=0x1110,𝜆=4 p=0x10,𝜆=2 p=0x1110,𝜆=4 p=0x1000,𝜆=4 p=0x1110,𝜆=4 p=0x10,𝜆=2 p=0x1110,𝜆=4
| | | | | | | | | | 𝐵=10···0 | | | 𝐵=10···0 |
| -------- | --- | -------- | --- | --------- | -------- | --- | -------- | --- | -------- | --- | --------- | -------- |
| 𝐵=10···0 | | 𝐵=10···0 | | 𝐵=110···0 | 𝐵=10···0 | | 𝐵=10···0 | | | | 𝐵=110···0 | |
𝑃01[0]=10···0 𝑃01[0]=10101010··· 𝑃01[0]=11001100··· 𝑃01[0]=10···0 𝑃01[0]=10101010··· 𝑃01[0]=11001100···
| | | | | 0 | 1 | | | | | 0 | 1 | |
| --- | --- | --- | ------------- | ------------- | --- | --- | --- | --- | --- | ------------- | ------------- | --- |
| | | | p=0x1001,𝜆=4 | p=0x1011,𝜆=4 | | | | | | p=0x1001,𝜆=4 | p=0x1011,𝜆=4 | |
| | | | 𝐵=10···0 | 𝐵=10···0 | | | | | | 𝐵=10···0 | 𝐵=10···0 | |
| | | | 𝑃01[0]=10···0 | 𝑃01[0]=10···0 | | | | | | 𝑃01[0]=10···0 | 𝑃01[0]=10···0 | |
(a) 1:Prefixmatchingsucceeds; 3:𝐵 𝜆 = 1 =11 (b) 1:Prefixmatchingsucceeds; 2:Levelmismatchbetween
c o m mon
shalloweranddeepernoderesolvedtotargetnode
| | | | | 𝜆 = 1 | | | | | | INTERSECT(•,•) | | |
| --- | --- | --- | --- | ----- | --- | --- | --- | --- | --- | -------------- | --- | --- |
3.2:𝐵c o m mon[1]=1
| | | | | | | | | p=0x1,𝜆=1 | | | p=0x1,𝜆=1 | |
| --- | --------- | --- | --- | --------- | --- | --- | --- | --------- | --- | --- | --------- | --- |
| | p=0x1,𝜆=1 | | ∩ | p=0x1,𝜆=1 | | | | | | ∩ | | |
| | 𝐵=110···0 | | | 𝐵=110···0 | | | | 𝐵=110···0 | | | 𝐵=110···0 | |
| | | | | | | | | 0 | | | 0 | |
| | 0 | 1 | | 0 | 1 | | | | 1 | | | 1 |
p=0x1000,𝜆=4 p=0x1110,𝜆=4 p=0x10,𝜆=2 p=0x1110,𝜆=4 p=0x1000,𝜆=4 p=0x1110,𝜆=4 p=0x10,𝜆=2 p=0x1110,𝜆=4
𝐵=10···0 𝐵=10···0 𝐵=110···0 𝐵=10···0 𝐵=10···0 𝐵=10···0 𝐵=110···0 𝐵=10···0
| | | | | | | | 𝑃01[0]=10···0 | | 𝑃01[0]=10101010··· | | | 𝑃01[0]=11001100··· |
| ------------- | --- | ------------------ | ------------- | ------------- | ------------------ | --- | ------------- | --- | ------------------ | ------------- | ------------- | ------------------ |
| 𝑃01[0]=10···0 | | 𝑃01[0]=10101010··· | | | 𝑃01[0]=11001100··· | | | | | | | |
| | | | | 0 | 1 | | | | | 0 | 1 | |
| | | | p=0x1001,𝜆=4 | p=0x1011,𝜆=4 | | | | | | p=0x1001,𝜆=4 | p=0x1011,𝜆=4 | |
| | | | 𝐵=10···0 | 𝐵=10···0 | | | | | | 𝐵=10···0 | 𝐵=10···0 | |
| | | | 𝑃01[0]=10···0 | 𝑃01[0]=10···0 | | | | | | 𝑃01[0]=10···0 | 𝑃01[0]=10···0 | |
(c) 1:Prefixmatchingsucceeds; 3:𝐵 𝜆 = 4 =1 (d) 1:Prefixmismatchdetected;subtreepruned,returnsnull
c o m mon
| | | | | 3.1 Leaf-levelbitmapintersection | | | | | | | | |
| --- | --- | --- | --- | -------------------------------- | --- | --- | --- | --- | --- | --- | --- | --- |
p=0x1110,𝜆=4
𝐵=10···0
𝑃01[0]=10001000···
(e)Finalintersectionresult
Figure3:Executiontraceoftheintersectionalgorithmdemonstratingprefix-basedpruningandbitmapconjunction.Path
(a)→(b)→(d)terminatesduetoprefixmismatch;path(a)→(c)→(e)completesvialeaf-levelintersection.Boldfaceanddashed
bordersmarkactivenodesateachrecursionstep;annotationsreferencealgorithmphasesfromListing1.
3.2 OtherSetOperations LevelMisalignment(Listing2,lines12–29).If𝐿.𝜆≠𝑅.𝜆,the
shallower(lessspecific)node𝑆mustdescendtothelevelofthe
ThetriestructureofPRISMextendsnaturallytosetunion(∪),differ-
ence(∖),andsymmetricdifference(△).Whereintersectionprunes deeper(morespecific)node𝐷.Thealgorithmextractsindex𝑖from
disjointsubtreesentirely,theseoperationshandlethemaccording 𝐷’sprefixatlevel𝑆.𝜆tolocate𝐷among𝑆’schildren.Ifthisslotis
unoccupied(𝑆.𝐵[𝑖]=0),theoperandsdonotoverlapthere:union
| to | their specific | semantics: | copying,merging, | | or discardingthe | | | | | | | |
| --- | -------------- | ---------- | ---------------- | --- | ---------------- | --- | --- | --- | --- | --- | --- | --- |
andsymmetricdifferenceclone𝑆andattachacloneof𝐷atposition
subtree.Listing2presentsageneralizedframeworkthatunifiesall
𝑖(line18),whereassetdifferencereturnsacloneof𝐿,sinceno
threeoperationsoverPRISM.Theproceduretraversesthetriere-
cursively,applyingoperation-specificlogicateachlevelaccording elementof𝐿isremoved(line19).Ifslot𝑖isoccupied,thealgorithm
tofourprincipalcases. processes𝑆’schildren:atposition𝑖,itrecursesonthecorresponding
childand𝐷(lines21–23);atallotherpositions,itclonesthechildfor
| Handling | | Empty Sets | (Listing | 2, lines | 2–7). The algorithm | | | | | | | |
| -------- | --- | ---------- | -------- | -------- | ------------------- | ----------------------------------------------------- | --- | --- | --- | --- | --- | --- |
| | | | | | | unionandsymmetricdifference,orforsetdifferenceonlyif𝑆 | | | | | | =𝐿 |
firsthandlesthedegeneratecaseswhereoneorbothoperandsare
(lines24–25).Foreachinspectedposition,𝑁.𝑃→[𝑗]isupdatedwith
null.Ifbotharenull,soistheresult.Ifonly𝐿isnull,unionand
symmetricdifferenceclone𝑅,whiledifferencereturnsnull:𝐿is theresult𝑐and𝑁.𝐵[𝑗]recordswhether𝑐isnon-null(cf.line28).
empty,sothedifferenceisempty.Ifonly𝑅isnull,allthreeclone Level-wiseProcessing(Listing2,lines30–48).If𝐿.𝜆 = 𝑅.𝜆,
bothnodeslieatthesamelevelandtheirchildrenareprocessed
𝐿.
jointly.First,thealgorithmcomputesthesharedchildpositions
| Disjoint | | Prefixes (Listing | 2, | lines 8–11). | Before descending, | | | | | | | |
| -------- | --- | ----------------- | --- | ------------ | ------------------ | --- | --- | --- | --- | --- | --- | --- |
viabitwiseANDontheirpresencebitmaps.Forthesepositions,it
thealgorithmcheckswhethertheprefixesoverlap.Fordisjoint
operands,unionandsymmetricdifferencecombinethetwosubtrees eitherappliestheoperation-specificbitwiseprimitivetothepayload
viamergeDisjoint,whereassetdifferencereducestoacloneof𝐿, bitmapswhenthenodesareatleaflevel(cf.applyinTable1),or
sincenoneof𝐿’selementsareremoved. recursesonthecorrespondingchildpointers.Apositionismarked
57
function SET_OP⟨op⟩(𝐿, 𝑅) Table1:Setoperation-specificbitwiseprimitive.
1
| | if 𝐿 | = null | and 𝑅 | = null | // Handling | | Empty | Sets | | | | | | |
| --- | ---- | ------ | ----- | ------ | ----------- | --- | ----- | ---- | --- | --- | --- | --- | --- | --- |
2
| 3 | return | null | | | | | | | | | | | | |
| --- | ------ | ------ | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| | | | | | | | | | | | | ∪ | ∖ △ | |
| 4 | if 𝐿 | = null | | | | | | | | | | | | |
5 return (op ∈{∪,△}) ? clone(𝑅) : null apply(𝑥,𝑦,op) 𝑥∨𝑦 𝑥∧¬𝑦 𝑥⊕𝑦
| | if 𝑅 | = null | | | | | | | | | | | | |
| --- | ---- | ------ | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
6
| 7 | return | clone(𝐿) | | | | | | | | | | | | |
| --- | ----------- | --------------- | --------- | ----------------- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 8 | // Disjoint | | Prefixes | | | | | | | | | | | |
| 9 | 𝑀← | prefixMask(𝐿.𝜆) | | ∧ prefixMask(𝑅.𝜆) | | | | | | | 𝐵 | | 𝑃 | |
| 10 | if (𝐿.𝑝∧𝑀) | | ≠ (𝑅.𝑝∧𝑀) | | | | | | | | | | | |
return op ∈{∪,△} ? mergeDisjoint(𝐿, 𝑅) : clone(𝐿) 0 1 2 … 61 62 63 0 1 2 3
11
12 if 𝐿.𝜆≠𝑅.𝜆 // Level Misalignment Node4 0 0 1 … 0 1 0 • • •
| 13 | (𝑆, | 𝐷) ←𝐿.𝜆<𝑅.𝜆 | | ? (𝐿, | 𝑅) : | (𝑅, 𝐿) | | | | | | | | |
| --- | ----------- | ---------------- | --------- | ----------- | -------- | ----------- | -------- | ------- | ------ | --- | ------ | ----- | --------- | ------- |
| 14 | 𝑁← | createNode(𝑆.𝜆, | | 𝑆.𝑝) | | | | | | | | | | |
| | | | | | | | | | | | 𝐵 | | 𝑃 | |
| 15 | leftShallow | | ← | (𝑆=𝐿) | | | | | | | | | | |
| | 𝑖← | extractBits(𝐷.𝑝, | | 𝑆.𝜆) | | | | | | | | | | |
| 16 | | | | | | | | | | 0 1 | 2 … 61 | 62 63 | 0 1 2 3 4 | … 14 15 |
| 17 | if | 𝑆.𝐵[𝑖]=0 | // no | overlap | at | 𝑖 | | | | | | | | |
| | | | | | | | | | Node16 | 1 0 | 1 … 0 | 1 0 | • • • • • | … |
| 18 | | return | op ∈{∪,△} | ? (clone(𝑆) | | with | clone(𝐷) | at 𝑖) | | | | | | |
| 19 | | | | : | clone(𝐿) | | | | | | | | | |
| 20 | for | each | set bit | 𝑗 in | 𝑆.𝐵 do | // overlap: | | descend | | | | | | |
| | if | 𝑗=𝑖 | | | | | | | | | 𝐵 | | 𝑃 | |
21
| 22 | | 𝑐← SET_OP⟨op⟩(leftShallow | | | | ? (𝑆.𝑃→[𝑗], | | 𝐷) | | | | | | |
| --- | --- | ------------------------- | --------- | --------- | ----- | ----------- | ------------ | --- | ------ | --- | ------ | ----- | ---------- | ----- |
| | | | | | | | | | | 0 1 | 2 … 61 | 62 63 | 0 1 2 … 61 | 62 63 |
| 23 | | | : (𝐷, | 𝑆.𝑃→[𝑗])) | | | | | | | | | | |
| | | | | | | | | | Node64 | 1 0 | 1 … 0 | 1 0 | • • … | • |
| 24 | | else if | op ∈{∪,△} | or | (op = | ∖ and | leftShallow) | | | | | | | |
clone(𝑆.𝑃→[𝑗])
| 25 | | 𝑐← | | | | | | | | | | | | |
| --- | --- | ------------- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| | | else continue | | | | | | | | | | | | |
26
27 𝑁.𝑃→[𝑗]←𝑐
Figure4:Memorylayoutofthemorphingnodes.Eachnode
| 28 | 𝑁.𝐵[𝑗]←𝑐≠ | | null | | | | | | | | | | | |
| --- | --------- | --- | ---- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
storesa64-bitbitmap𝐵indicatingpresentchildrenanda
| 29 | return | 𝑁.𝐵=0 | ? | null : | collapseIfSingleton(𝑁) | | | | | | | | | |
| --- | ------ | ----- | --- | ------ | ---------------------- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
// Level-wise Processing payload array 𝑃. Node4 and Node16 pack payload entries
30
| | 𝑁← | createNode(𝐿.𝜆, | | 𝐿.𝑝∧𝑀) | | | | | | | | | | |
| --- | --- | --------------- | --- | ------ | --- | --- | --- | --- | ------------------------------------------------- | --- | --- | --- | --- | --- |
| 31 | | | | | | | | | compactly(arrowsshowbitmap-to-arraymapping),while | | | | | |
32 𝐵 ←𝐿.𝐵∧𝑅.𝐵
| | common | | | | | | | | Node64usesdirectindexing.Bulletsmarkoccupiedslots. | | | | | |
| --- | ------ | -------- | --- | ------ | --- | --------- | ------ | --- | -------------------------------------------------- | --- | --- | --- | --- | --- |
| 33 | for | each set | bit | 𝑖 in 𝐵 | do | // Handle | common | | | | | | | |
common
34 if isLeaf(𝐿)
| | 𝑁.𝑃01[𝑖]← | | apply(𝐿.𝑃01[𝑖], | | 𝑅.𝑃01[𝑖], | op) | | | | | | | | |
| --- | --------- | --- | --------------- | --- | --------- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
35
𝑁.𝐵[𝑖]←𝑁.𝑃01[𝑖]≠0
| 36 | | | | | | | | | 4 MORPHINGNODES | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --------------- | --- | --- | --- | --- | --- |
37 else
38 𝑁.𝑃→[𝑖]← SET_OP⟨op⟩(𝐿.𝑃→[𝑖], 𝑅.𝑃→[𝑖]) Workloadsspreadoccupancyunevenly:somenodesaredense,some
39 𝑁.𝐵[𝑖]←𝑁.𝑃→[𝑖]≠ null aresparse,andnosinglelayoutservesboth.Storingall2𝑏payload
| | // Handle | left-only | | children | (all | three | operations) | | | | | | | |
| --- | --------- | --------- | --- | -------- | ---- | ----- | ----------- | --- | --- | --- | --- | --- | --- | --- |
40
41 for each set bit 𝑖 in 𝐿.𝐵∧¬𝑅.𝐵 do entriespernodewastesmemoryonsparsenodes,whileauniformly
42 𝑁.𝑃[𝑖]← clone(isLeaf(𝐿) ? 𝐿.𝑃01[𝑖] : 𝐿.𝑃→[𝑖]) compactlayoutslowsaccesstodenseones.Sizingcontainerstotheir
43 𝑁.𝐵[𝑖]←1 loadisestablishedpractice:ART[19]growsradixnodesthrough
44 if op ∈{∪,△} // Handle right-only children capacityclassesandRoaring[9,22]switchescontainerrepresen-
| | for | each | set bit | 𝑖 in | 𝑅.𝐵∧¬𝐿.𝐵 | do | | | | | | | | |
| --- | --- | ---- | ------- | ---- | -------- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
45
46 𝑁.𝑃[𝑖]← clone(isLeaf(𝑅) ? 𝑅.𝑃01[𝑖] : 𝑅.𝑃→[𝑖]) tationsasapartitionfills.PRISMusesthreenodetypes(Figure4):
47 𝑁.𝐵[𝑖]←1 Node4andNode16store4or16childrenincompactarrays;Node64
48 return 𝑁.𝐵=0 ? null : collapseIfSingleton(𝑁) storesupto64bydirectindexing.
Listing2:Setoperations∪,∖,and△ Unlike ART and Roaring, which couple their operations to
thecontainerrepresentation,PRISMexposesanode-type-agnostic
interface.Everynodetypecarriesthesamefixed-width64-bitpres-
encebitmap𝐵,wherebit𝑖recordswhetherchild𝑖ispresent.The
operationsthatdetectsharedchildrenandprunetheremaining
| in | the result | node’s | presence | | bitmap | 𝑁.𝐵 only | if it | contributes: | | | | | | |
| --- | ---------- | ------ | -------- | --- | ------ | -------- | ----- | ------------ | --- | --- | --- | --- | --- | --- |
subtreesread𝐵alone,independentofnodetype.
| a | non-zero | bitmap | at leaf | level | or a non-null | | child | (cf. line 36 | | | | | | |
| --- | --------- | ------- | ------- | --------- | ------------- | ------ | ------- | ------------ | --- | --- | --- | --- | --- | --- |
| and | line 39). | It then | handles | positions | | unique | to each | operand: | | | | | | |
union(∪)andsymmetricdifference(△)clonechildrenfromboth 4.1 NodeStructureandAccessPatterns
sides(lines40–43andlines44–47),whereasdifference(∖)clones Eachnodecarriesaprefix𝑝,alevelindicator𝜆,anda64-bitpres-
onlychildrenuniqueto𝐿(lines40–43).Thepresencebitmap𝑁.𝐵 encebitmap𝐵.Withthis,anynode,regardlessofitstype,answers
isupdatedtomarkthesechildren(cf.line43andline47). whetherchild𝑖ispresentwithasinglebitteston𝐵,whichisallthat
Toreducecloningcost,weimplementcopy-on-write(COW): detectingsharedchildrenandpruningsubtreesrequires.Thetypes
eachnodemaintainsareferencecount,incrementedonsharedcopy differonlyinhow𝐵mapstothepayloadarray𝑃;Figure4shows
anddecrementedonrelease.Nodesareduplicatedonlywhenmod- thismappingandListing3showshowitisrealizedefficientlyusing
ifiedduringrecursivedescent.Thisavoidsunnecessaryduplication availableinstructions.Growthselectsamongthembyobserved
whenlargesubtreesremainunchanged,asiscommonin∪,∖,and density,recoveringmemoryatsparsenodeswithoutalteringthe
| △. | | | | | | | | | algorithms. | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | ----------- | --- | --- | --- | --- | --- |
58
| function | ACCESS_CHILD(𝑣, | 𝑖) | | 4.3 SIMDVectorization | | | |
| -------- | --------------- | --- | --- | --------------------- | --- | --- | --- |
1
| if 𝑣 | is Node4 or | Node16 | | | | | |
| ------ | -------------------- | ------------- | ----- | ------------------------------------------------------- | --- | --- | --- |
| 2 | | | | SIMDprocessesmanybitmappositionsperinstruction,andPRISM | | | |
| 3 pos← | popcount(𝑣.𝐵∧(2𝑖−1)) | // Compressed | index | | | | |
exposesthreeopportunitiestoexploitthisacrossallnodetypes.
| 4 return | 𝑣.𝑃[pos] | | | | | | |
| -------- | -------- | --- | --- | --- | --- | --- | --- |
5 else // v is Node64 First,leafsetoperationsarebitwiseovermanybitmaps;thefixed-
return // Direct indexing width𝑃01layoutmapstowideregisters,soAVX-512handleseight
| 6 | 𝑣.𝑃[𝑖] | | | | | | |
| --- | ------ | --- | --- | --- | --- | --- | --- |
Listing3:Morphing-nodechildaccess 64-bit bitmaps per instruction. Second, synchronized traversals
| | | | | yieldacommonbitmap𝐵 | | thatdoublesasamaskforvector- | |
| --- | --- | --- | --- | ------------------- | --- | ---------------------------- | --- |
common
| | | | | izedloadsandstores,touchingonlypositionswith𝐵 | | | [𝑖]=1. |
| --- | --- | --- | --- | --------------------------------------------- | --- | --- | ------ |
common
Third,vectorizedcomparisonsmarkthenon-zeroresultpositions
| 1 function | INSERT_NODE(𝑣, | 𝑖, 𝑐) | | | | | |
| ---------- | -------------- | ----- | --- | --- | --- | --- | --- |
toemit,cuttingbranchmispredictionsininnerloops.
| 2 𝑚←1≪𝑖 | // Bit for | position i | | | | | |
| ------- | ---------- | ---------- | --- | --- | --- | --- | --- |
Realizingallthreeoneverynodetypeisnotautomatic:Node4
| 3 if 𝑣 | is Node4 or | Node16 | | | | | |
| ------ | ----------- | ------ | --- | --- | --- | --- | --- |
popcount(𝑣.𝐵) // Current child count andNode16storechildrenincompressedform,breakingthecon-
4 𝑛←
pos← popcount(𝑣.𝐵∧(𝑚−1)) // Compressed index tiguousloadstheopportunitiesaboveassume.PRISMkeepsasin-
5
6 present←(𝑣.𝐵∧𝑚)≠0 glekernelacrosslayoutsbyreconcilingthecompressedformwith
| 7 if | 𝑛< capacity(𝑣) | or present | | | | | |
| ---- | -------------- | ---------- | --- | --- | --- | --- | --- |
maskedmemoryoperations:
| 8 | upsert(𝑣.𝑃, pos, | 𝑐, present) // Shift-insert | or | | | | |
| --- | ---------------- | --------------------------- | --- | --- | --- | --- | --- |
overwrite (1) mask_expandloaduspreadscompressedchildrenintovector
9 𝑣.𝐵←𝑣.𝐵∨𝑚
lanesaccordingtothepresencebitmap
10 else
| | | | | (2) positionsabsentin𝐵 | common | arezeroed | |
| --- | --------------------- | ---------- | --------------- | ---------------------- | ------ | --------- | --- |
| 11 | 𝑣′← getNextAndCopy(𝑣) | // Grow to | next size class | | | | |
INSERT_NODE(𝑣′, (3) bitwiseoperations(AND/OR/XOR)runacrosstheregister
| 12 | return | 𝑖, 𝑐) | | | | | |
| --- | ------ | ----- | --- | --- | --- | --- | --- |
else // v is Node64 (4) mask_compressstoreuwritesresultsbackincompressedform
13
14 𝑣.𝐵←𝑣.𝐵∨𝑚
WhenanodegrowstoNode64,storageiscontiguousandthe
| 15 𝑣.𝑃[𝑖]←𝑐 | // Direct | write | | | | | |
| ----------- | --------- | ----- | --- | --- | --- | --- | --- |
maskedpathgiveswaytodirectAVX-512access:eightbitmapsload,
| 16 return | 𝑣 | | | | | | |
| --------- | --- | --- | --- | --- | --- | --- | --- |
operate,andstoreinonepass.Throughout,PRISMusesAVX-512
Listing4:Morphing-nodeinsertion
atfullregisterwidthandfallsbacktoscalarprocessingforsparser
sets.
5 EVALUATION
Node4andNode16storechildrencontiguouslyincompressed
WeevaluatePRISMagainststrongbaselinesfromeveryalgorith-
form.Tolocatechild𝑖,wemapitsbitmappositiontoacompressed
| | | | | mic category | surveyed in Section | 7, covering sorted | and SIMD |
| --------- | -------------------------------------------- | --- | --- | ------------ | ------------------- | ------------------ | -------- |
| index:pos | = popcount(𝐵∧(2𝑖−1)).Thiscountsthesetbitsbe- | | | | | | |
merge-basedintersection,hierarchicalrepresentations,hash-based
foreposition𝑖in𝑂(1)timeusingahardwarepopulationcount
methods,andcompressedbitmaps.ForPRISM,weconsiderboth
instruction(Listing3,lines3–4),keepingonlyoccupiedchildrenin
PRISM64,whichusesonlyNode64layouts,andthefullmorphing-
memory.
nodedesign.
Node64dropstheindirection:child𝑖sitsatposition𝑖in𝑃(List-
Ourprimarycompetitorsaretwo64-bitadaptationsofRoar-
ing3,line6).Accessisdirect,atthecostofallocatingall64slots
ing[9,22]1:Roaring(C++)partitionskeysbytheirupper32bits
regardlessofoccupancy.
viaastd::mapandstoresthelowerhalvesinthestandard32-bit
Roaringstructure;Roaring(C)usesa48/16-bitsplit,indexingthe
4.2 DynamicNodeGrowth
upper48bitsthroughanART[19]thatmapstoRoaringcontainers
Insertionkeepseachnodesizedtoitsloadbygrowingitonlywhen fortheremaining16-bitsuffixes.
capacityisreached.Listing4givestheprocedure,branchingon ForSIMDmerge-basedintersection,weincludeSIMDGallop-
nodetype. ing[20],BMiss[17],andQFilter[15],whichexploitvectorized
ForNode4andNode16,welocatethecompressedindexposwith
comparisonstointersectsortedsequences.Forhierarchicalrepre-
popcount(𝐵∧(𝑚−1)),where𝑚=2𝑖isthebitforposition𝑖,and
sentations,weincludeHERO[31]andthebalanced-treebaseline
testwhetherchild𝑖isalreadypresent.Ifthenodehasroomorthe std::set,ared-blacktree.Weexcludethecompressedbinarytries
childisalreadypresent,upsertwrites𝑐atpos,shiftinglaterentries (CBT)[2]becauseitsimplementationtargets32-bitkeysandreturns
foranewchildoroverwritinganexistingone,andsetsbit𝑖in incorrectresultsonour64-bitinputs.Forhash-basedmethods,we
𝐵(lines7–9).Otherwisethenodeisfull:wegetanodefromthe includeFESIA[32]andtsl::ordered_set(TSL)2.Forcompressed
bitmaps,weretainRoaringandEWAH[21]3,whichencodesets
nextsizeclass,copytheexistingchildren,andreinsertrecursively
(lines11–12).Anodeundergoesatmosttwosuchtransitionsover asrun-lengthcompressedbitvectors.
| its lifetime | (Node4 to Node16 | to Node64), so | growth adds only | | | | |
| ------------ | ---------------- | -------------- | ---------------- | ------------------ | ------------------------------------ | --- | --- |
| | | | | ExperimentalSetup. | Experimentsrunontwoplatformsspanning | | |
amortizedconstantcostperinsertion.Node64needsnoindirection:
itsetsbit𝑖in𝐵andwrites𝑐to𝑃[𝑖](lines14–15). x86-64andARM;Table2listshardwareandcompilerdetails.On
Node16→Node64 AMDRyzen7950X,weenableallvectorextensionsuptoAVX-512,
| Growth | optimization. | The | transition ex- | | | | |
| ------ | ------------- | --- | -------------- | --- | --- | --- | --- |
pandscompressedchildrenintodirect-indexedpositions.Where
1https://github.com/RoaringBitmap/CRoaring(v4.6.1,accessed2026-06-30)
available,AVX-512acceleratesthis:each8-bitbitmapsegmentis
2https://github.com/Tessil/ordered-map(v1.2.0,accessed2026-06-30)
processedwithmaskedloadsandthevpexpandqinstruction. 3https://github.com/lemire/EWAHBoolArray(v0.8.0,accessed2026-06-30)
59
Table2:Experimentalplatforms. Withincreasingoverlap,PRISMmostlydominatesonthedense
andgriddistributions.However,onthedensedistribution,oncethe
AMDRyzen7950X AVX-512,Cache:32K/1M/64M𝑠 firstoperandexceeds104elements,Roaringbeginstooutperform
64GBDDR5 PRISM.Atthisscale,atleastoneoperandconsistsentirelyofbitmap
GCC14.2andClang20.1 containers,enablingRoaring’sspecializedbitwiseANDroutines
AppleM3Ultra NEON,Cache:128K𝑝/64M𝑢 atminimaloverhead.PRISMsupportsanalogousnode-levelbitwise
256GBLPDDR5 operations, but its trie layout requires loading and intersecting
Clang21.2 substantiallymorenodes.
Athigheroverlap,onthesparseandpointerdistributions,PRISM
𝑠SharedL3.𝑝PerP-core(64KperE-core).𝑢SharedbyP-cores(4MbyE-cores).
fallsbehindtheSIMDmerge-basedapproaches.Bothdistributions
spreadelementsacrossmanynodeswithoutforminglargecontigu-
implementbothAVX2andAVX-512kernelsfortheSIMDmerge- ousregions,soPRISMcannotexploitsubtreepruningandmust
basedmethods,andreportthefasterone.TheAppleM3Ultrahas instead traverse and allocate result nodes individually; by con-
no hand-vectorized kernels, so we omit the SIMD merge-based struction,thepointerdistributionbehaveslikeasparseoneover
methodsthere.Allbuildsuse-O3,with-march=nativeonx86-64 asmalleruniverse.SIMDmerge-basedalgorithmsavoidthisover-
and-march=armv8-a+simdonARM.Eachexperimentruns100 headentirely:sincetheyoperateonflat,contiguous,sortedarrays,
timesonasinglethreadandreportsaveragethroughput.Dueto theyreducetheintersectiontoatightscanwithnopointerchasing
memorylimitations,werunTSLonlyuptosetsizesof105. ornodeallocation,whichischeaperthanwalkingandrebuilding
PRISM’strienodebynode.OnAppleM3Ultra,theSIMDmerge-
DataDistributions. Weusefoursyntheticdistributionsof64-bit
basedmethodsareunavailable,andhash-basedapproachestake
integers:
theleadinstead,avoidingthesameper-nodetreeoverheadthrough
Dense:thecontiguousrange[1,𝑛]. 𝑂(1)lookups.Skewedworkloadsflipthis:whenonesideismuch
Grid:eachbyteofeachkeydrawnuniformlyfrom[1,14][25]. smallerthantheother,PRISMwins.
Pointer:clusteredkeyssimulatingtupleidentifiers,combining
arandombasefrom{𝑖⋅216∶𝑖∈[0,220)}witharandomoffset 5.1.2 OtherSetOperations. Figure6reportsthespeedupofPRISM
from[0,212). overstd::setandRoaringonsetoperationsatoverlapcoefficients
Sparse:uniformrandomsamplesfrom[0,264). of0%,50%,and100%.Forthedense,grid,andpointerdistributions,
PRISMoutperformsbothcompetitorsonnearlyalloperationsat
OverlapCoefficient. Toquantifysimilaritybetweentwosets𝐴 lowoverlapcoefficients;thesespeedupsmainlycomefromPRISM’s
and𝐵,weusetheoverlapcoefficient COWsemantics,whichletitsharewholedisjointsubtreeswiththe
|𝐴∩𝐵| resultinsteadoftraversingandmaterializingthem.Thisoptimiza-
overlap(𝐴,𝐵)= . tionfadesastheoperandsbegintooverlap:theythenoccupythe
min(|𝐴|,|𝐵|)
samenodesanddifferonlyinwhichelementstheymark,soPRISM
Forsetoperations,thefirstoperandisdrawnfromoneofthedistri-
musttraverseandmergethosenodesindividually.Speedupsrelative
butionsabove;thesecondisconstructedbysamplingafractionof
toRoaringthereforeshrinkastheoverlapcoefficientgrows.The
thefirstoperand’selementsequaltothetargetoverlapcoefficient,
effectismostpronouncedforthedensedistributionwithidentical
thenfillingtheremainingpositionswithuniformrandom64-bit setslargerthan104elements,wherePRISM’strielayoutrequires
integers.Thus,atlowoverlap,thesecondoperandisdominatedby
mergingsubstantiallymorenodes,increasingcachepressureand
uniformkeys.
reducingthroughput.Forthesparsedistribution,thespeedupis
smaller:PRISMperformsonparwithstd::setandisroughly10×
5.1 SetOperations
fasterthanRoaring,asPRISMandRoaringmusttraverseand
Asourdatastructureisprimarilydesignedtooptimizesetopera- mergemorenodesorcontainers.
tions,weevaluatethemacrossdistributionsandoverlapcoefficients
onthemachinesdescribedabove. 5.2 InsertionPerformanceandThreshold-based
Intersection
5.1.1 Intersection. Figure5reportsthefastestalgorithmpersize
combination,brokendownbydistributionandoverlapcoefficient Beyondsetoperations,twomoreaspectsmatterforintegerset
onAMDRyzen(AVX-512)andAppleM3Ultra(noSIMDkernels). structures:insertionperformanceandthreshold-basedintersection.
ForRoaring,weconsiderboththeC++andCinterfacesandboth
5.2.1 InsertionPerformance. Figure7reportsinsertionthroughput
processingorders,reportingthebest-performingoneperconfigu-
fororderedandunorderedsequencesandper-elementmemory.
ration.
We include only structures that support elementwise insertion
Whenthetwosetsaremostlydisjoint,PRISMnearlyalways
withoutneedingthewholesetatonce.Whereavailable,weuse
outperformsthecompetitors:itshierarchicallayoutenablesaggres-
bulkinsertioninterfaces,whichcachethelast-accessedcontainer
siveearlyterminationwhensubtreessharenokeys.Thisismost
ornodetofavororderedanddenseworkloads.
pronouncedondensedistributions,wherelargecontiguousregions
canbeskippedentirely,andalsoholdsacrossthegridandpointer OrderedInsertion. Onthedensedistribution,PRISM64comes
distributionsonbothplatforms.OnAppleM3Ultra,PRISMand closesttoEWAH,whichstillleadsthroughrun-lengthencoding;
Roaringachievecomparablethroughputatzerooverlap. ongrid,itmatchesorexceedsEWAHupto105 elementsbefore
60
AMD Ryzen Apple M3 Ultra
dense sparse grid pointer dense sparse grid pointer
0%
25%
50%
75%
100%
108
106
104
102
108
106
104
102
108
106
104
102
108
106
104
102
108
106
104
102
102 104 106 108 102 104 106 108 102 104 106 108 102 104 106 108 102 104 106 108 102 104 106 108 102 104 106 108 102 104 106 108
Number of elements in A
B
ni
stnemele
fo
rebmuN
std::set TSL EWAH Roaring FESIA HERO SIMDGalloping QFilter BMiss PRISM
Figure5:Best-performingintersectionalgorithmbydistributionandoverlapcoefficient,onAMDRyzenandAppleM3Ultra
(PRISM64isomitted).WeexcludeSIMDmerge-basedmethodsonAppleM3Ultra,whichwerunwithouthand-vectorized
kernels.Sparsedistributionsarenotmeasuredforsetsof108elements.
dense sparse grid pointer
A ∪
B
A
∖
B
A
△
B
106
104 102
100 10−2
106
104
102
100
10−2
106 104
102
100
10−2
102 104 106 102 104 106 102 104 106 102 104 106
set size |A| = |B| (log scale)
)elacs
gol(
MSIRP
fo
pudeepS
Roaring(C++),whileClangreachesparity.Forthepointerdistri-
bution,PRISMandPRISM64landbetweenstd::setandRoaring.
Onthesparsedistribution,PRISMstaysthefastestcompressed
structure,aheadofbothRoaringvariantsandEWAH,sinceits
morphingnodesavoidover-allocationforisolatedkeys;PRISM64
degradesatscaleandfallsbehindtheRoaringvariants;amongall
structures,onlystd::setisfasterthanPRISMhere.
UnorderedInsertion. WeexcludeEWAHhere,asitrequiressorted
input.Ondenseandgriddistributions,PRISM64achievesthehigh-
estthroughput:mostkeysfitwithinasingleNode64upto103
elementsondenseand102elementsongrid,andthroughputpeaks
before further node allocations bring it down. PRISM pays for
std::set Roaring overlap 0% 50% 100% morphing-nodegrowth,andboth Roaringvariantsstayahead
ofstd::setbyupto2×inthemid-range.Onpointerandsparse
Figure6:SpeedupofPRISMoverstd::setandRoaringon distributions,std::setleadsupto103 elementsbutdegradesat
setoperationsacrossdistributionsandoverlapcoefficients largercardinalitiesduetobalanced-treemaintenance;PRISM64and
forequallysizedsetsonAMDRyzen. PRISMthentakeover.Roaring(C++)showsthelowestthroughput,
sincedispersedkeysforceseparatecontainerallocations.Onthe
pointerdistribution,throughputrecoversslightlypast106elements
oncesorted-arraycontainersconverttobitmapcontainers.
fallingbehindatlargercardinalities.PRISMtrailsPRISM64due
tomorphingoverhead,butstillmatchesorbeatsbothRoaring MemoryConsumption. TherightpanelofFigure7reportsper-
variants,whichpayfordynamiccontainerexpansion.Roaring(C) elementmemoryafterallinsertions.EWAHhasoneofthesmallest
iscompiler-sensitive:GCCroughlyhalvesitsthroughputversus footprintsonthedense,grid,andpointerdistributionsthrough
61
| | | Ordered | | | | | | Unordered | | Memory consumption | |
| ---- | --------------- | ------- | ---------------------- | --- | ----- | ---- | --------------- | ---------------------- | ----- | ------------------ | ----- |
| | AMD Ryzen (gcc) | | Apple M3 Ultra (clang) | | | | AMD Ryzen (gcc) | Apple M3 Ultra (clang) | | | |
| 600M | | | | | | 500M | | | | 100 | |
| | | | | | esned | 400M | | | esned | 0.1 | esned |
| 400M | | | | | | 300M | | | | | |
200M
| 200M | | | | | | | | | | )elacs gol( ]B[ tnemele rep setyB 0.0001 | |
| ---- | --- | --- | --- | --- | --- | --- | --- | --- | --- | ---------------------------------------- | --- |
100M
| | 0 | | | | | 0 | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
]s/stresni[ tuphguorhT
| 500M | | | | | | 400M | | | | 30 | |
| ---- | --- | --- | --- | --- | ---- | ---- | --- | --- | ---- | --- | ---- |
| 400M | | | | | | 300M | | | | 10 | |
| 300M | | | | | dirg | | | | dirg | | dirg |
| 200M | | | | | | 200M | | | | 3 | |
| 100M | | | | | | 100M | | | | | |
1
| | 0 | | | | | 0 | | | | | |
| ---- | --- | --- | --- | --- | ------- | --- | --- | --- | ------- | --- | ------- |
| 200M | | | | | | 60M | | | | 300 | |
| 150M | | | | | retniop | | | | retniop | | retniop |
| | | | | | | 40M | | | | 100 | |
| 100M | | | | | | | | | | 30 | |
| | | | | | | 20M | | | | 10 | |
50M
| | 0 | | | | | 0 | | | | 3 | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
100M
| 60M | | | | | | 60M | | | | | |
| --- | --- | --- | --- | --- | ------ | --- | --- | --- | ------ | --- | ------ |
| | | | | | esraps | | | | esraps | 1M | esraps |
| 40M | | | | | | 40M | | | | | |
10k
| 20M | | | | | | 20M | | | | 100 | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| | 0 | | | | | 0 | | | | | |
102 104 106 108 102 104 106 108 102 104 106 108 102 104 106 108 102 104 106 108
| | | Number of elements | | | | | | Number of elements | | Number of elements | |
| --- | --- | ------------------ | --- | -------- | ------------- | --- | ----------- | ------------------ | ----- | ------------------ | --- |
| | | | | std::set | Roaring (C++) | | Roaring (C) | EWAH PRISM64 | PRISM | | |
Figure 7: Insertion throughput (left: ordered; middle: unordered) and per-element memory (right) across platforms and
distributions.Thedashedlinemarksthesizeoftheuncompresseddata(8bytesperelement).Roaringisdotted,asitsreported
footprintcountsonlytheserializedbitset.
intersectionsize.Throughputdropsasthethresholdgrows,sincea
| )elacs gol( ]s/spo[ tuphguorhT | dense | sparse | | grid | | pointer | | | | | |
| ------------------------------ | ----- | ------ | --- | ---- | --- | ------- | --- | --- | --- | --- | --- |
largerfractionoftheintersectionmustbecomputedbeforetermi-
106 nation.Theoverlapcoefficientbarelyaffectsthroughput:PRISM
50%
| 104 | | | | | | | | leadsonthedenseandgriddistributionsandtrailsQFilterand | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | ------------------------------------------------------ | --- | --- | --- |
| 102 | | | | | | | | SIMDGallopingonthepointerandsparsedistributions.Those | | | |
twodistributionsscatterelementsacrossmorenodes,sotraversal
106
| | | | | | | | 100% | issuesmorememoryaccesses. | | | |
| --- | --- | --- | --- | --- | --- | --- | ---- | ------------------------- | --- | --- | --- |
104
102
| | 11 % % % | % % %11 % % | % % % %11 | % % % % | % %11 % | % % % % | % | | | | |
| --- | -------- | ----------- | --------- | ------- | ------- | ------- | --- | --- | --- | --- | --- |
5 10 25 50 100 5 10 25 50 100 5 10 25 50 100 5 10 25 50 100 6 REAL-WORLDCASESTUDIES
Threshold
Weevaluatethreereal-worldscenarios:conjunctiveanddisjunctive
| | PRISM | QFilter | SIMDGalloping | std::set | std::unordered_set | | | | | | |
| --- | ----- | ------- | ------------- | -------- | ------------------ | --- | --- | --- | --- | --- | --- |
queriesontheStarSchemaBenchmark(SSB),asimulatedtrigram-
basedinvertedindexonTPC-H,andinverted-listintersectionon
Figure8:Threshold-basedintersectionthroughputonAMD
theClueWeb09dataset.
Ryzenfortwosetsofonemillionelementseach,acrossdis-
Wecompareagainstrepresentativesofeachmajorcategory:the
tributions,overlapcoefficients,andthresholds.
orderedcontainerstd::set;thehash-basedTSLandFESIA[32];
thehierarchicalCBT[2],whoseimplementationislimitedto32-
bitelementsbutapplicableheresinceallelementsfallwithinthat
run-lengthcompression,butislargestonsparsedata.Onthedense
range,andHERO[31];thecompressedbitmapsEWAH[21]and
distribution,everystructureexceptstd::setandEWAHconverges
Roaring(CandC++interfaces)[9,22];andtheSIMD-accelerated
toacomparableper-elementcost.Thegrid,pointer,andsparse
BMiss[17],QFilter[15],andSIMDGalloping[20].Hash-based
distributionsshowtheadvantageofmorphingnodes:PRISMuses
competitorsiterateoverthesmallestsetandprobetheothers.Roar-
about8×lessmemoryperelementthanPRISM64onpointerand
ingkeepsitsnativecontainerorderhere,sinceprocessingsmallest-
sparse,andabout4×ongrid.BothRoaringfootprintsareunderes-
firstslowsitdown.Measurementsexcludepreparationtimesuch
timates,reflectingonlytheserializedbitsetsizeratherthanthefull
asbuildingorsorting.
in-memoryrepresentation.
| 5.2.2 | Threshold-basedIntersection. | | | Insomescenarios,onedoes | | | | | | | |
| ----- | ---------------------------- | --- | --- | ----------------------- | --- | --- | --- | ---------------------------- | --- | --- | --- |
| | | | | | | | | 6.1 CaseStudy:FilteringonSSB | | | |
notneedthefullintersectionoftwosets,onlywhetheritssize
exceedsagiventhreshold.Figure8reportsthreshold-basedinter- SSB joins a central fact table (LINEORDER) with four dimension
section throughput on AMD Ryzen for two sets of one million tables.OnourAMDmachine,weevaluatethefilteringportionof
elementseach,acrossdistributions,overlapcoefficients,andthresh- queriesQ1.1,Q2.1,Q3.4,andQ4.1[23,29]atscalefactors1,10,and
olds.Wesetthethresholdtoasingleelement(atestfornon-empty 100.Q1.1andQ2.1reducetotheintersectionofthreeandtwosets,
intersection)orto 1%,5%, 10%,25%,50%, or100% oftheactual respectively,whileQ3.4andQ4.1adddisjunctivepredicatesand
62
Table3:Querythroughput(ops/s)onSSBacrossscalefactors. Table4:Throughput(ops/s)forTPC-Htrigramindexqueries
Bestresultpercolumn(excludingPRISM64)isbold;PRISM64 across scale factors. Best result per column (excluding
isPRISMwithoutmorphing,isolatingitseffect. PRISM64)isbold;PRISM64isPRISMwithoutmorphing,iso-
latingitseffect.
| Algorithm | | | Q1.1 | | | Q2.1 | | | | | | |
| --------- | --- | --- | ---- | ------ | --- | ---- | --- | --------- | --- | --------- | --------- | ------ |
| | | | | | | | | Algorithm | | chocolate | firebrick | salmon |
| | | | 1 | 10 100 | | 1 10 | 100 | | | | | |
PRISM 13.7M 11.8M 4.1M 21.9M 5.0M 396K 1 10 100 1 10 100 1 10 100
| PRISM64 | | 15.7M | 13.2M | 5.2M | 27.9M | 6.2M | 441K | | | | | |
| ------- | --- | ----- | ----- | ---- | ----- | ---- | ---- | ----- | --- | -------- | ----------- | -------------- |
| | | | | | | | | PRISM | | 120K 12K | 1K 120K 12K | 1K 152K 17K 2K |
Roaring(C) 1.9M 1.9M 36K 5.1M 638K 206K PRISM64 104K 11K 1K 106K 11K 1K 161K 16K 2K
| Roaring(C++) | | 2.3M | 2.1M | 739K | 2.0M | 367K | 91K | | | | | |
| ------------ | --- | ---- | ---- | ---- | ---- | ---- | --- | ---------- | --- | ------ | ---------- | -------------- |
| | | | | | | | | Roaring(C) | | 50K 5K | 469 89K 9K | 872 53K 5K 533 |
CBT 198K 187K 150K 206K 115K 23K Roaring(C++) 13K 1K 146 11K 1K 124 49K 5K 451
| FESIA | | | 220 | 23 | 1 313K | 72K | 19K | | | | | |
| ----- | --- | --- | --- | --- | ------ | --- | --- | --- | --- | ------ | --------- | ------------ |
| | | | | | | | | CBT | | 9K 701 | 68 9K 704 | 67 13K 1K 98 |
HERO 14K 615 24 858K 183K 40K FESIA 407 34 3 443 35 3 798 63 5
| EWAH | | 5.6M | 5.4M | 1.5M | 1.2M | 287K | 68K | | | | | |
| ---- | --- | ---- | ---- | ---- | ---- | ---- | --- | ---- | --- | ------ | --------- | ------------ |
| | | | | | | | | HERO | | 2K 152 | 13 2K 154 | 13 5K 309 25 |
std::set 202K 212K 174K 693K 55K 3K EWAH 20K 2K 192 20K 2K 192 39K 4K 391
| TSL | | 549K | 591K | 382K | 1.6M | 118K | 4K | | | | | |
| --- | --- | ---- | ---- | ---- | ---- | ---- | --- | -------- | --- | ------ | -------- | ---------- |
| | | | | | | | | std::set | | 415 26 | 2 457 32 | 2 628 35 3 |
BMiss(AVX2) 1.4M 1.3M 1.0M 3.1M 330K 30K TSL 611 50 4 660 51 5 1K 94 8
| QFilter(AVX-512) | | 1.6M | 1.5M | 1.2M | 4.4M | 438K | 42K | | | | | |
| ---------------- | --- | ---- | ---- | ---- | ---- | ---- | --- | ----------- | --- | ------- | --------- | -------------- |
| | | | | | | | | BMiss(AVX2) | | 11K 714 | 62 15K 2K | 118 13K 591 56 |
SIMDGalloping(v1) 2.1M 2.0M 1.5M 3.6M 391K 38K QFilter(AVX-512) 10K 733 64 13K 1K 105 12K 675 64
| | | | | | | | | SIMDGalloping(v1) | | 13K 1K | 89 15K 2K | 113 27K 1K 117 |
| --------- | --- | --- | ---- | --- | --- | ---- | --- | ----------------- | --- | ------ | --------- | -------------- |
| Algorithm | | | Q3.4 | | | Q4.1 | | | | | | |
| | | 1 | 10 | 100 | | 1 10 | 100 | | | | | |
PRISM
| PRISM | | 2.9M | 279K | 26K | 507K | 87K | 52K | | | | | |
| ------- | --- | ---- | ---- | --- | ---- | ---- | --- | --- | ------- | --- | --- | --- |
| PRISM64 | | 2.9M | 343K | 32K | 510K | 121K | 52K | | PRISM64 | | | |
Roaring (C)
| Roaring(C) | | 1.2M | 332K | 39K | 406K | 99K | 57K | | Roaring (C++) | | | |
| ------------ | --- | ---- | ---- | --- | ---- | --- | --- | --- | ------------- | --- | --- | --- |
| Roaring(C++) | | 1.7M | 328K | 31K | 341K | 73K | 30K | | EWAH | | | |
CBT
| FESIA | | 489K | 42K | 1K | 328 | 73 | 37 | SIMDGalloping (v1) | | | | |
| -------- | --- | ---- | --- | --- | ---- | --- | --- | ------------------ | ---------------- | --- | --- | --- |
| HERO | | 543K | 56K | 4K | 1K | 314 | 184 | | QFilter (AVX512) | | | |
| EWAH | | 465K | 49K | 4K | 130K | 30K | 14K | | HERO | | | |
| std::set | | 131K | 14K | 1K | 349 | 75 | 34 | | BMiss (AVX2) | | | |
| TSL | | 733K | 74K | 3K | 1K | 330 | 143 | | TSL | | | |
FESIA
std::set
| | | | | | | | | | | 10−2 10−1 | 100 101 | 102 103 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --------- | ------- | ------- |
thusalsorequiresetunion.Table3reportsthethroughputforeach Throughput [ops/s] (log scale)
queryacrossallscalefactors.
On the pure intersection queries Q1.1 and Q2.1, PRISM and Figure9:IntersectionthroughputonClueWeb09postinglists
PRISM64achievethehighestthroughputateveryscalefactor,ahead (AMDRyzen).Eachpointintersects4listsrandomlydrawn
ofRoaringandEWAHby2–8×inmostconfigurationsandahead fromthe200largest;boxessummarize100draws.
ofthegeneral-purposebaselinesstd::setandTSLbymorethan
anorderofmagnitude.PRISM64staysaheadofPRISMthroughout,
byuptoabout1.3×withnoconsistenttrendacrossscalefactors. namescontaineveryquerytrigram.Table4reportsthroughput
OntheunionqueriesQ3.4andQ4.1,PRISMleadsatscalefactor acrossthreerepresentativequerystrings.
1,buttrailsRoaring(C)at10and100,wherethebitmapmerge PRISM and PRISM64 achieve the highest throughput across
allconfigurations.Roaring(C)andRoaring(C++)exhibitdata-
winsoncenearlyeverynodemustbecombined.Weattributethisto
dependentperformance:whiletheyachievecomparablethroughput
thestructureoftheSSBdata:theelementsaredrawnfromasmall
universe,sotheysharelongcommonprefixesanddifferonlyin onthesalmonquery,Roaring(C)is8×fasterthanRoaring(C++)
theirlow-orderbits.Theunionmustthereforemergenearlyevery onthefirebrickquery.Throughputscalesnearlylinearlywith
node,precludingtheCOWshortcutandincreasingthenumberof theinverseofthescalefactorforallstructures,confirmingthatthe
bottleneckisproportionaltosetsize.EWAH,theSIMDmerge-based
accessednodes,whichraisescachepressureandlowersthroughput.
methods,andCBTformthenexttier,trailingPRISMbyroughly4
| CBT, BMiss, | QFilter, | and | SIMDGalloping | | do | not support | set | | | | | |
| ----------- | -------- | --- | ------------- | --- | --- | ----------- | --- | --- | --- | --- | --- | --- |
unionandarethereforeomitted. to13×,whileHERO,FESIA,std::set,andTSLaretheslowest,an
orderofmagnitudeormorebehind.
6.2 CaseStudy:TPC-HTrigramIndex
| | | | | | | | | 6.3 | CaseStudy:InvertedListsonClueWeb09 | | | |
| ------------------------------------------------- | --- | --- | --- | --- | --- | --- | --- | --- | ---------------------------------- | --- | --- | --- |
| Wesimulateaninvertedindexbybuildingatrigramindex4 | | | | | | | on | | | | | |
thepart.namecolumnoftheTPC-Hdataset5.Eachpartnameis To cover a broader range of real-world workloads, we evaluate
decomposedintocontiguousthree-charactersequences,andamap inverted-listintersectionontheClueWeb09dataset6.Wedownload
apre-builtindex7,selectthe200largestpostinglists,andintersect
fromtrigramstopart-identifiersetsisconstructed.Toevaluatea
4randomlychosenlistsatatime,repeatingthedraw100times.
querystring,wedecomposeitintotrigramsandperforma𝑘-way
intersectionoverthecorrespondingsets,returningallpartswhose Theselistsrangefrom8.2to35.5millionentries,withamedianof
4https://www.postgresql.org/docs/current/pgtrgm.html(accessed2026-06-30) 6https://lemurproject.org/(accessed2026-06-30)
5https://www.tpc.org/tpch/(accessed2026-06-30) 7http://searchivarius.org/personal/data-sets/clueweb09gap(accessed2026-06-30)
63
11.6millionandameanof13.1million.AsFigure9shows,PRISM segmentsandsummarizeseachsegmentwithacompactbitmap
reaches the highest throughput. It is faster than both Roaring signature.Intersectionthenrunsintwophases:abitwiseANDof
variantsandfasterthanPRISM64onmostintersections. thesignaturearraysdoesBloom-stylefilteringandprunesnon-
overlappingsegmentswithouttouchingthepayloads;aSIMDker-
7 BACKGROUNDANDRELATEDWORK nelthenintersectswhateversurvivesviaallpairwisecomparisons
Efficientsetintersectionoverfixed-sizeintegersisabuildingblock withinasegment.
ofqueryprocessingindatabases,informationretrieval,anddata
CompressedBitmaps. Analternativestrategyencodesaset𝑆 ⊆
analytics.Wefirstsurveydirectcompetitors,organizedbyrepresen-
[0,𝑈)asalength-𝑈bitvector.Intersectionthenreducestoword-
tation:sortedarrays,hierarchicalrepresentations,hash-basedmeth-
parallelANDoperations.However,rawbitmapsareimpracticalfor
ods,andcompressedbitmaps.Wealsodiscussthesetcontainment
largesparseuniverses.Run-lengthcompressionschemessuchas
joinproblem,inwhichsetintersectionappearsasasubroutine.
BBC[1],WAH[30],EWAH[21],andCONCISE[11]addressthisby
SortedArraysandMerge-BasedIntersection. Sortedarraysarethe encodingrunsofidenticalbitswhilepreservingbitwiseoperations
standardintegersetrepresentation,intersectedbylinearmergeor on the compressed representation. Roaring bitmaps [9] take a
bysearchingoneoperandintheother.Classicalworkreducescom- differentapproachandcombineper-chunkcontainerselectionwith
parisonsviagallopingsearchandadaptivemergealgorithms[3– SIMD-optimizedoperations[22].Abroadexperimentalstudyby
6,12,16].Morerecentworktargetsinstructionthroughputwith Wang et al. [29] confirms Roaring as the fastest bitmap-based
SIMD,whichcomparesmultipleelementspercycle:BMiss[17], intersectionmethod,whileinvertedlistsaregenerallymorespace-
SIMDGalloping[20],andQFilter[15]. efficient. WhereRoaringdispatchesoncontainertypeatevery
chunk,PRISMpresentsonenode-type-agnosticbitmapinterface.
HierarchicalRepresentations. Treaps,balancedtrees,andskip
listsgivelogarithmicsearchwithefficientupdates[7,14,24,26]. SetContainmentJoins. Setintersectionisalsopartofsetcontain-
Triesgofurther,sincesharedprefixesletstructuralsimilaritybe- mentjoins,whichjointablesonset-valuedattributesunderasubset
tweensetsdoalgorithmicworkdirectly.ChenandShen[10]encode constraint.Existingsolutions[8,18]buildatrieoveronerelation
multiplesetsintoatrieandreduceintersectiontointervalcom- andaninvertedindexovertheother,thenintersecttheposting
parisonandbinarysearch.Closesttoourworkaretwotrie-based lists retrieved by trie traversal to produce the join output. This
approaches: ArroyueloandCastillo[2]representintegersetsas trie-over-inverted-filedesignwasfirstproposedforsingle-relation
compressedbinarytriesandintersectthemviasynchronizeddepth- containmentsearch[27]andlateradaptedtojoins.PRISMdoesnot
first traversal. Subtrees that cannot contribute to the result are addresscontainmentjoinsdirectly,butits𝑘-wayintersectioncan
prunedalongtheway.Eachnodebranchesonasinglebit,sonavi- acceleratetheposting-liststep.
gationmovesonelevelperbitandreliesonrankoversuccinctbit
vectorsratherthanbitmaparithmetic.Descentandmembership 8 CONCLUSION
areseparateprimitives,andthedesignfavorsspaceoverthrough-
WepresentedPRISM,aprefix-basedintegersetthatexploitsthe
put.PRISMinsteadexposeseverynodethroughonefixed-width
hierarchical structure of 64-bit keys for efficient set operations.
bitmap,soasingleword-parallelANDcoversseverallevelsatonce,
PRISMorganizeskeysintoatrieoffixed-widthsegments,with
whereabinarytriecanonlydescendonebitatatime.HERO[31]
nodesrecordingchildoccupancyasbitmaps.Everysetoperation
combinesahierarchicalstructurewithbitmapsummariesforgraph
thenbecomesasinglesynchronizedtop-downtraversal.Nodepre-
workloads.Itpartitionseachadjacencylistintofixed-sizesegments
fixesandbitmapsaloneidentifysharedanddisjointsubtrees,so
acrossafixednumberoflevelsandencodessegmentpresenceat
weneverexamineindividualelements,andwevectorizeleaf-level
eachlevelasabitmap.Together,thesebitmapsformasetintersec-
processing with SIMD. The operations differ only in how they
tionbitmaptree(SIB-tree)thatfiltersnon-overlappingsegments
treatthesesubtrees:intersectionprunesdisjointonesandextends
early.Itslevelsareheterogeneous,itsdepthisfixedratherthan
tothe𝑘-waycasebysimultaneousdescent;union,difference,and
data-dependent,andallprocessingisscalar.PRISMdiffersoneach
symmetric difference use copy-on-write sharing to handle sub-
point:everynodeateverydepthexposesthesamefixed-width
treesexclusivetooneoperand.Morphing-nodelayoutssizeeach
bitmap,sooneAND-and-recursestephandlespruning,navigation,
nodetoitsoccupancyandcompresssparseregionsbyupto8×,
andprocessingatonce;adaptiveprefixcompressionmakesdepth
atminorcosttodensethroughput.PRISMisthefastestmethod
data-dependent;andtheuniformlayoutletsSIMDoperateboth
weevaluatedforpairwiseintersection.Itleadsatlowoverlapon
withinandacrosslevels.
mostdistributionsandstayscompetitivewhereSIMDmerge-based,
Hash-BasedMethods. Whenorderedaccessisnotrequired,hash bitmap,andhash-basedmethodstakeover.Threereal-worldcase
tablesmakeadifferenttrade-off.Thestandardapproachbuildsa studiessupportthesegains:conjunctiveanddisjunctivequeries
hashtableoverthesmallersetandprobesitwiththelargerset; onSSB,a𝑘-waytrigram-indexworkloadonTPC-H,andinverted-
expectedtimeis𝑂(𝑛)with𝑚≤𝑛,regardlessofvaluedistribution. listintersectiononClueWeb09.Acrossallthree,PRISMleadson
DingandKönig[13]hash-partitionsetsintocache-friendlyblocks, intersection-heavyworkloads,anditremainscompetitiveonunion
enablingword-parallelcomparisonsandreducingprobeoverhead. queriesonSSBatlargerscales.Theseresultsshowthatorganiz-
Thetrade-offislosingsortedorderandthestructuralpropertiesthat ingintegerdatahierarchicallyexposessharedanddisjointregions,
hierarchicalmethodsrelyon. FESIA[32]sitsbetweenbitmap,hash- andthatthestructurealoneisenoughtoidentifythemandprune
based,andmerge-basedmethods.Ithash-partitionseachsetinto redundantcomputation.
64
REFERENCES 8,3(2014),293–304.
[1] GennadyAntoshenkov.1995.Byte-alignedbitmapcompression.InProceedings [18] RavindranathJampaniandVikramPudi.2005.UsingPrefix-TreesforEfficiently
DCC’95DataCompressionConference.IEEEComputerSociety,476. ComputingSetJoins.InDASFAA(LectureNotesinComputerScience),Vol.3453.
[2] DiegoArroyueloandJuanPabloCastillo.2023.Trie-CompressedAdaptiveSet Springer,761–772.
Intersection.InCPM(LIPIcs),Vol.259.SchlossDagstuhl-Leibniz-Zentrumfür [19] ViktorLeis,AlfonsKemper,andThomasNeumann.2013.Theadaptiveradixtree:
Informatik,1:1–1:19. ARTfulindexingformain-memorydatabases.InICDE.IEEEComputerSociety,
[3] RicardoA.Baeza-Yates.2004. AFastSetIntersectionAlgorithmforSorted 38–49.
Sequences.InCPM (LectureNotesinComputerScience),Vol.3109.Springer, [20] DanielLemire,LeonidBoytsov,andNathanKurz.2016.SIMDcompressionand
400–408. theintersectionofsortedintegers.Softw.Pract.Exp.46,6(2016),723–749.
[4] JérémyBarbay,AlejandroLópez-Ortiz,andTylerLu.2006.FasterAdaptiveSet [21] DanielLemire,OwenKaser,andKamelAouiche.2010.Sortingimprovesword-
IntersectionsforTextSearching.InWEA(LectureNotesinComputerScience), alignedbitmapindexes.DataKnowl.Eng.69,1(2010),3–28.
Vol.4007.Springer,146–157. [22] DanielLemire,OwenKaser,NathanKurz,LucaDeri,ChrisO’Hara,François
[5] JérémyBarbay,AlejandroLópez-Ortiz,TylerLu,andAlejandroSalinger.2009. Saint-Jacques,andGregorySsi-Yan-Kai.2018.Roaringbitmaps:Implementation
Anexperimentalinvestigationofsetintersectionalgorithmsfortextsearching. ofanoptimizedsoftwarelibrary.Softw.Pract.Exp.48,4(2018),867–895.
ACMJ.Exp.Algorithmics14,Article7(2009),24pages. [23] PatrickE.O’Neil,ElizabethJ.O’Neil,XuedongChen,andStephenRevilak.2009.
[6] JonLouisBentleyandAndrewChi-ChihYao.1976.AnAlmostOptimalAlgorithm TheStarSchemaBenchmarkandAugmentedFactTableIndexing.InTPCTC
forUnboundedSearching.Inf.Process.Lett.5,3(1976),82–87. (LectureNotesinComputerScience),Vol.5895.Springer,237–252.
[7] GuyE.BlellochandMargaretReid-Miller.1998.FastSetOperationsUsingTreaps. [24] WilliamW.Pugh.1990.SkipLists:AProbabilisticAlternativetoBalancedTrees.
InSPAA.ACM,16–26. Commun.ACM33,6(1990),668–676.
[8] PanagiotisBouros,NikosMamoulis,ShenGe,andManolisTerrovitis.2016.Set [25] StefanRichter,VictorAlvarez,andJensDittrich.2015. ASeven-Dimensional
containmentjoinrevisited.Knowl.Inf.Syst.49,1(2016),375–402. AnalysisofHashingMethodsanditsImplicationsonQueryProcessing.Proc.
[9] SamyChambi,DanielLemire,OwenKaser,andRobertGodin.2016.Betterbitmap VLDBEndow.9,3(2015),96–107.
performancewithRoaringbitmaps.Softw.Pract.Exp.46,5(2016),709–719. [26] RaimundSeidelandCeciliaR.Aragon.1996.RandomizedSearchTrees.Algo-
[10] YangjunChenandWeixinShen.2016.Anefficientmethodtoevaluateintersec- rithmica16,4/5(1996),464–497.
tionsonbigdatasets.Theor.Comput.Sci.647(2016),1–21. [27] ManolisTerrovitis,SpyrosPassas,PanosVassiliadis,andTimosK.Sellis.2006.
[11] AlessandroColantonioandRobertoDiPietro.2010.Concise:Compressed’n’ Acombinationoftrie-treesandinvertedfilesfortheindexingofset-valued
ComposableIntegerSet.Inf.Process.Lett.110,16(2010),644–650. attributes.InCIKM.ACM,728–737.
[12] ErikD.Demaine,AlejandroLópez-Ortiz,andJ.IanMunro.2000.Adaptiveset [28] ToddL.Veldhuizen.2014.Triejoin:ASimple,Worst-CaseOptimalJoinAlgorithm.
intersections,unions,anddifferences.InSODA.ACM/SIAM,743–752. InICDT.OpenProceedings.org,96–106.
[13] BolinDingandArndChristianKönig.2011.FastSetIntersectioninMemory. [29] JianguoWang,ChunbinLin,YannisPapakonstantinou,andStevenSwanson.
Proc.VLDBEndow.4,4(2011),255–266. 2017.AnExperimentalStudyofBitmapCompressionvs.InvertedListCompres-
[14] LeonidasJ.GuibasandRobertSedgewick.1978.ADichromaticFrameworkfor sion.InSIGMODConference.ACM,993–1008.
BalancedTrees.InFOCS.IEEEComputerSociety,8–21. [30] KeshengWu,EkowJ.Otoo,andArieShoshani.2006.Optimizingbitmapindices
[15] ShuoHan,LeiZou,andJeffreyXuYu.2018. SpeedingUpSetIntersections withefficientcompression.ACMTrans.DatabaseSyst.31,1(2006),1–38.
inGraphAlgorithmsusingSIMDInstructions.InSIGMODConference.ACM, [31] BoyuYang,WeiguoZheng,XiangLian,YuzhengCai,andX.SeanWang.2024.
1587–1602. HERO:AHierarchicalSetPartitioningandJoinFrameworkforSpeedingupthe
[16] FrankK.HwangandShenLin.1972. ASimpleAlgorithmforMergingTwo SetIntersectionOverGraphs.Proc.ACMManag.Data2,1(2024),29:1–29:25.
[32] JiyuanZhang,YiLu,DanieleG.Spampinato,andFranzFranchetti.2020.FESIA:
DisjointLinearly-OrderedSets.SIAMJ.Comput.1,1(1972),31–39.
AFastandSIMD-EfficientSetIntersectionApproachonModernCPUs.InICDE.
[17] HiroshiInoue,MoriyoshiOhara,andKenjiroTaura.2014.FasterSetIntersection
IEEE,1465–1476.
withSIMDinstructionsbyReducingBranchMispredictions.Proc.VLDBEndow.
65