Nebel, Markus E, Neumann, Elisabeth and Wild, Sebastian ORCID: 0000-0002-6061-9177
(2016)
Median-of-k Jumplists and Dangling-Min BSTs.
.
Text
1609.08513v3.pdf - Author Accepted Manuscript Download (1MB) | Preview |
Abstract
We extend randomized jumplists introduced by Br\"onnimann et al. (STACS 2003) to choose jump-pointer targets as median of a small sample for better search costs, and present randomized algorithms with expected $O(\log n)$ time complexity that maintain the probability distribution of jump pointers upon insertions and deletions. We analyze the expected costs to search, insert and delete a random element, and we show that omitting jump pointers in small sublists hardly affects search costs, but significantly reduces the memory consumption. We use a bijection between jumplists and "dangling-min BSTs", a variant of (fringe-balanced) binary search trees for the analysis. Despite their similarities, some standard analysis techniques for search trees fail for dangling-min trees (and hence for jumplists).
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Additional Information: | appears in ANALCO 2019 |
Uncontrolled Keywords: | cs.DS, cs.DS, E.1 |
Depositing User: | Symplectic Admin |
Date Deposited: | 21 Oct 2019 15:12 |
Last Modified: | 19 Jan 2023 00:21 |
DOI: | 10.1137/1.9781611975505.8 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3058939 |