Abstract-I detta dokument presenterar vi vår GPU genomförande av kvoten filter, en kompakt datastruktur utformad för att genomföra ungefärliga medlemskap frågor. Det quotient filtret liknar det mer välkända Bloom filtret; men förutom att ställa in och medlemskap frågor, quotient filtret stöder också raderingar och sammanslagning filter utan att kräva rehashing av datamängden. Dessutom kan quotientfiltret utökas till att omfatta räknare utan att minnesavtrycket ökar. Detta dokument beskriver vårt GPU-implementation av två typer av quotient filter: standard quotient filter och rangand-select-based quotient filter. Vi beskriver parallelliseringen av alla filteroperationer, inklusive en jämförelse av de fyra olika metoder vi utformat för parallellisering av quotientfilterkonstruktion. För att lösa detta problem fann vi att vi behövde en operation som liknade en parallell scan, men för icke-associativa operatörer. Ett resultat av detta arbete är en mängd olika metoder för att beräkna parallella scan-liknande operationer på en icke-associativ operatör. För frågor om medlemskap uppnår vi en överföring på upp till 1,13 miljarder poster/sekund för rank-och-select-baserat kvotfilter: en upphastighet på 3 gånger över BloomGPU-filtret. Vår snabbaste filterbyggmetod uppnår en hastighetsökning på 2,1-3,1x över BloomGPU, med en toppgenomströmning på 621 miljoner objekt/sekund, och en hastighet på 516 miljoner objekt/sekund för en 70% full filter. Vi finner dock att våra filter inte utför inkrementella uppdateringar lika snabbt som BloomGPU-filtret. För en sats på 2 miljoner poster utför vi inkrementella inlägg med en hastighet av 81 miljoner poster/sekund - en 2,5x nedgång jämfört med BloomGPU: s genomströmning av 201 miljoner poster/sekund. Det quotienta filtrets minnesavtryck är jämförbart med ett Bloom-filters.
Nyligen fanns det också ett GPU-baserat genomförande av kvotfilter REF.
Quotient Filters: Approximate Membership Queries on the GPU
{'venue': '2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)', 'journal': '2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)', 'mag_field_of_study': ['Computer Science']}