Set skärningspunkt är en grundläggande operation i informationssökning och databassystem. Detta dokument introducerar linjära rymddatastrukturer för att representera uppsättningar så att deras skärningspunkt kan beräknas på ett i värsta fall effektivt sätt. I allmänhet, givet k (förbearbetade) uppsättningar, med helt n element, kommer vi att visa hur man beräknar deras skärningspunkt i förväntad tid O(n/ ε w + kr), där r är skärningsstorleken och w är antalet bitar i ett maskin-ord. Dessutom introducerar vi en mycket enkel version av denna algoritm som har svagare asymptotiska garantier men presterar ännu bättre i praktiken; både algoritmer överträffar toppmoderna tekniker för både syntetiska och verkliga datamängder och arbetsbelastningar.
Det är uppenbart att denna gräns bygger på ett stort värde av w. I REF presenteras uppsättningen av linjär rymddatastruktur som gör det möjligt att beräkna skärningspunkten i O(m+n)/sqrt(w)+2r).Denna algoritm presterar bättre i praktiken.
Fast Set Intersection in Memory
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}