Den dynamiska approximativa medlemskap problemet ber att representera en uppsättning S i storlek n, vars delar tillhandahålls på ett on-line-sätt, stödja medlemskap frågor utan falska negativa och med en falsk positiv hastighet som mest. Det vill säga, medlemskapsalgoritmen måste vara korrekt på varje x  på S, och kan fela med sannolikhet som mest på varje x /  på S. Vi studerar en välmotiverad, men otillräckligt utforskad, variant av detta problem där storleken n av uppsättningen inte är känd i förväg. Befintliga optimala approximativa medlemsdata strukturer kräver att storleken är känd i förväg, men i många praktiska scenarier är detta inte ett realistiskt antagande. Dessutom, även om den slutliga storleken n av uppsättningen är känd i förväg, är det önskvärt att ha minsta möjliga utrymme användning också när det nuvarande antalet infogade element är mindre än n. Vårt bidrag består av följande resultat: • Vi visar en super-linjär gap mellan utrymmet komplexitet när storleken är känd i förväg och utrymmet komplexitet när storleken inte är känd i förväg. När storleken är känd i förväg, är det välkänt att  på log(1/ ) bitar av utrymme är nödvändiga och tillräckliga (Bloom '70, Carter et al. - "78". - Jag vet inte. Men när storleken inte är känd i förväg, visar vi att minst (1 − o(1))n log(1/ ) +  på log n) bitar av utrymme måste användas. I synnerhet måste det genomsnittliga antalet bitar per element bero på mängdens storlek. • Vi visar att vårt utrymme är trångt och till och med kan matchas av en mycket effektiv datastruktur. Vi presenterar en datastruktur som använder (1+o(1))n log(1/ )+O(n log n) bitar av utrymme för att approximera någon uppsättning av någon storlek n, utan att behöva veta n i förväg. Vår datastruktur stöder medlemskap frågor i konstant tid i värsta fall med hög sannolikhet, och stöder tillägg i förväntad amortized konstant tid. Dessutom kan det vara "de-amortized" att stödja även infogar i konstant tid i värsta fall med hög sannolikhet genom att bara öka sin rymdanvändning till O(n log(1/ ) + n log log n) bitar.
Pagh, Segev och Wieder REF visade att om storleken n inte är känd i förväg måste minst (1 − o(1))n log 1 ε + (n log n) bitar av utrymme användas.
How to Approximate a Set without Knowing Its Size in Advance
{'venue': '2013 IEEE 54th Annual Symposium on Foundations of Computer Science', 'journal': '2013 IEEE 54th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}