Vi visar hur man representerar uppsättningar i en linjär rymddatastruktur så att uttryck som involverar fackföreningar och korsningar av uppsättningar kan beräknas på ett i värsta fall effektivt sätt. Detta problem har tillämpningar i t.ex. Datainsamlings- och databassystem. Vi överväger främst RAM-modellen för beräkning, och uppsättningar av maskinord, men även våra resultat i I/O-modellen. På ett RAM med ordstorlek w, ett speciellt fall av vårt resultat är att skärningspunkten mellan m (förbearbetade) uppsättningar, som innehåller n element totalt, kan beräknas i förväntad tid O(n(log w) 2 /w + km), där k är antalet element i skärningspunkten. Om den första av de två termerna dominerar, är detta en faktor w 1‐o(1) snabbare än standardlösningen för att slå samman sorterade listor. Vi visar en cellsond som är lägre än tidsbindningen (n/(wm log m) + (1 − log k w )k), vilket innebär att vår övre gräns är nästan optimal för små m. Vår algoritm använder en ny kombination av ungefärliga uppsättningar och parallellism på ordnivå.
Bille m.fl. REF presenterar en datastruktur som kan beräkna skärningspunkten mellan t-uppsättningar av total storlek n i förväntad tid O( n(log 2 w)/w + kt + log w), där k är storleken på utdata.
Fast evaluation of union-intersection expressions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}