Hittills har alla samtidiga sökstrukturer som kan stödja tidigare frågor haft djup logaritmiska i m, antalet element. Detta dokument introducerar SkipTree, en ny samtidig sökstruktur som stöder tidigare frågor i amorterade förväntade O(log log u + c) steg, tillägg och raderingar i O(c log u) och med O(m) utrymme, där u är storleken på nyckelutrymmet och c är innehållet under den senaste tiden. SkipTrie är en probabilistiskt balanserad version av en y-fast trie som består av en mycket ytlig skiplist från vilken slumpmässigt utvalda element sätts in i en hash-table baserad x-fast trie. Genom att infoga nycklar i x-snabb-trie probabilistically, eliminerar vi behovet av ombalansering, och kan ge en låsfri linjärizable implementation. Såvitt vi vet är vårt bevis på SkipTries avskrivna förväntade prestanda det första beviset för en trädbaserad datastruktur.
För samtidiga sökdatastrukturer som säkerställer tidigare frågor, det arbete som ligger närmast vårt är Skip-Tree REF, som tillåter föregångare frågor i amortized förväntade O(logglogg u + γ ) steg, och infogar och raderingar i O (γ log u) tid, där u är storleken på nyckeln utrymme, och γ är en övre gräns vid strid.
The SkipTrie: low-depth concurrent search without rebalancing
{'venue': "PODC '13", 'journal': None, 'mag_field_of_study': ['Computer Science']}