Ungefärliga uppsättningen medlemsdata strukturer (ASMDS) är allmänt förekommande i datorer. De byter ut en tunn, ofta liten, felprocent ( ) mot stora utrymmesbesparingar. Den kanoniska ASMDS är Bloom filtret, som stöder uppslag och tillägg men inte raderingar i sin enklaste form. Cuckoo filter (CFs), en nyligen föreslagna klass av ASMDSs, lägga till borttagning stöd och ofta använda färre bitar per objekt för lika. Detta arbete introducerar Morton filtret (MF), en ny AS-MDS som introducerar flera viktiga förbättringar för CFs. Liksom CFs, MFs stöder uppslag, insättningar och deletions, men förbättra sina respektive genomgångar med 1,3× till 2,5×, 0,9× till 15,5×, och 1,3× till 1,6×. MF:er uppnår dessa förbättringar genom att (1) införa ett komprimerat format som gör det möjligt att lagra ett logiskt glest filter kompakt i minnet, (2) utnyttja koncisa inbäddade metadata för att beskära onödiga minnesåtkomster, och (3) kraftigt partiska tillägg för att använda en enda hashfunktion. Med dessa optimeringar, lookups, införanden och borttagningar kräver ofta bara tillgång till en enda hårdvara cache linje från filtret. Dessa förbättringar är inte på en förlust i utrymme effektivitet, eftersom MFs brukar använda jämförbar med något mindre utrymme än CFs för samma.
Ett annat optimerat Cuckoo filter som heter Morton filtret presenteras i REF.
Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}