Vi föreslår en metod för att hålla en ordbok datastruktur, som kartlägger nycklar till värden, i anda av Bloom Filters. Utrymmeskraven i ordboken vi föreslår är mycket mindre än för en hashtable. Vi tillåter lagring n nycklar, varje mappad till värde som är en sträng av k bitar. Vår föreslagna metod kräver nk + o(n) bitar utrymme för att lagra ordboken, och O (n) tid för att producera datastrukturen, och gör det möjligt att svara på en medlem fråga i O(1) minne sonder. Ordbokens storlek beror inte på tangenternas storlek. Att minska datastrukturens rymdbehov är dock till en viss kostnad. Vår ordbok har en liten sannolikhet för ett fel i sidan. När vi försöker få värdet för en nyckel som lagras i ordboken får vi alltid rätt svar. Men när vi testar för medlemskap i ett element som inte lagras i ordboken, kan vi få ett felaktigt svar, och när vi begär värdet av ett sådant element kan vi få ett visst slumpmässigt värde. Vår metod bygger på att lösa ekvationer i GF (2 k ) och med hjälp av flera hashfunktioner. En annan viktig fördel med vår föreslagna metod är att vi inte behöver använda sofistikerade hashfunktioner. Vi behöver bara parvis oberoende hashfunktioner. Vi föreslår också en datastruktur som kräver bara nk bits utrymme, har O(n 2 ) förbehandlingstid, och har en O (log n) frågetid. Dessa datastrukturer kräver dock en enhetlig hashfunktion. För att ersätta ett Bloom Filter av n element med en felproability på 2 – k, kräver vi nk + o (n) minne bitar, O(1) frågetid, O (n) förbehandlingstid, och endast parvis oberoende hash funktion. Även den mest avancerade tidigare kända Bloom Filter skulle kräva nk + O(n) utrymme, och en enhetlig hash funktioner, så vår metod är betydligt mindre utrymme förbrukar särskilt när k är liten. Vår föreslagna ordbok kan ersätta Bloom Filters, och har många program. Några programexempel är ordböcker för lagring av dåliga lösenord, differentialfiler i databaser, Internet caching och distribuerade lagringssystem.
Resultatet av Porat REF är att en rymdanvändning av nr + o(n) bitar är möjlig med O(1) frågetid.
An Optimal Bloom Filter Replacement Based on Matrix Solving
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}