Online List Labeling with Near-Logarithmic Writes
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911870028349440 |
|---|---|
| author | Seybold, Martin P. |
| author_facet | Seybold, Martin P. |
| contents | In the Online List Labeling problem, a set of $n \leq N$ elements from a totally ordered universe must be stored in sorted order in an array with $m=N+\lceil\varepsilon N \rceil$ slots, where $\varepsilon \in (0,1]$ is constant, while an adversary chooses elements that must be inserted and deleted from the set.
We devise a skip-list based algorithm for maintaining order against an oblivious adversary and show that the expected amortized number of writes is $O(\varepsilon^{-1}\log (n) \operatorname{poly}(\log \log n))$ per update. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_04467 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Online List Labeling with Near-Logarithmic Writes Seybold, Martin P. Data Structures and Algorithms In the Online List Labeling problem, a set of $n \leq N$ elements from a totally ordered universe must be stored in sorted order in an array with $m=N+\lceil\varepsilon N \rceil$ slots, where $\varepsilon \in (0,1]$ is constant, while an adversary chooses elements that must be inserted and deleted from the set. We devise a skip-list based algorithm for maintaining order against an oblivious adversary and show that the expected amortized number of writes is $O(\varepsilon^{-1}\log (n) \operatorname{poly}(\log \log n))$ per update. |
| title | Online List Labeling with Near-Logarithmic Writes |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.04467 |