Write-Optimized Skip Lists
| Autor: | Helen Xu, Tyler Mayer, Rob Johnson, Simon Mauras, Michael A. Bender, Martin Farach-Colton, Cynthia A. Phillips |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
High probability
Skip list Computer science 0102 computer and information sciences 02 engineering and technology Data structure Binary logarithm 01 natural sciences Combinatorics 010201 computation theory & mathematics 020204 information systems 0202 electrical engineering electronic engineering information engineering Self-organizing list Arithmetic Block size Auxiliary memory |
| Zdroj: | PODS |
| DOI: | 10.1145/3034786.3056117 |
| Popis: | The skip list is an elegant dictionary data structure that is commonly deployed in RAM. A skip list with N elements supports searches, inserts, and deletes in O(log N) operations with high probability (w.h.p.) and range queries returning K elements in O(log N + K) operations w.h.p.A seemingly natural way to generalize the skip list to external memory with block size B is to "promote" with probability 1/B, rather than 1/2. However, there are practical and theoretical obstacles to getting the skip list to retain its efficient performance, space bounds, and high-probability guarantees.We give an external-memory skip list that achieves write-optimized bounds. That is, for 0 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|