patternMinor
Should one limit the maximum level of a skip list node?
Viewed 0 times
themaximumlevellimitnodeskiponeshouldlist
Problem
In Skip Lists: A Probabilistic Alternative to Balanced Trees by Pugh he suggests different strategies for choosing the level of an inserted node. One such strategy, called fix the dice, limits the level to our previous highest level plus one if a higher level was randomly chosen.
What are the practical implications of choosing this strategy, especially for large skip lists and those with p < 1/2?
I imagine it could lead to a higher than usual fanout, but without all too dramatic effects, especially if deletions are as common as insertions after some growth (since that would minimize the effect of lower than usual levels after that initial growth).
Any educated speculation or hints to already existing analyses are welcome.
What are the practical implications of choosing this strategy, especially for large skip lists and those with p < 1/2?
I imagine it could lead to a higher than usual fanout, but without all too dramatic effects, especially if deletions are as common as insertions after some growth (since that would minimize the effect of lower than usual levels after that initial growth).
Any educated speculation or hints to already existing analyses are welcome.
Solution
Contrary to what Pugh says in that paper, I don't believe the "fix the dice" strategy has any impact on the stochastic analysis of skip list performance.
The strategy demotes (reduces the level) of a newly-created item to one more than the current maximum level in the skip list, if the random level assignment would have produced a higher level. Let's call such an item a demoted item.
Observe that the skip list cannot contain two demoted items at the same level. One of them would have to have been created first, and that would prevent the other one from having been demoted to that level. (Items are never demoted after they are created, so even if deletions entirely empty some level, higher-level items continue to have the same level. One could imagine a strategy which also demoted existing items in such a case, but even then it would be impossible to have two demoted items at the same level.)
The level of an item is limited to $MaxLevel$ (using Pugh's terminology), which means that there are at most $MaxLevel$ demoted items in the skip list. Pugh suggests choosing $MaxLevel$ as $log_{p^{-1}}N$ where $N$ is the expected maximum number of elements in the skip list. In practice, we might use a fixed constant, or we might use $log_{p^{-1}}M$ where $M$ is the maximum size that the skip list has ever reached (assuming we use an implementation where $MaxLevel$ can be incremented). In any case, we expect that $MaxLevel$ is $O(\log n)$.
Now, let's say that $\mathscr{E}(l)$ is the expected number of items at level $l$ without die-fixing and $\mathscr{E}'(l)$ is the expected number in the die-fixed skip list. Die-fixing could cause at most $l-1$ items at level $l$ to be demoted to another level (because there are only $l-1$ lower levels, each of which can have at most one demoted item) and it could cause at most $1$ item at a higher level to be demoted to $l$. So:
$$\mathscr{E}'(l) \in [\mathscr{E}(l)-l-1, \mathscr{E}(l)+1]$$
Since $\mathscr{E}(l) = n\mathscr{P}(l)$, where $\mathscr{P}(l)$ is the probability for a random item to be at level l (analogue $\mathscr{P}'(l)$ for the die-fixed list), we can estimate
$$\mathscr{P}'(l) \in [\mathscr{P}(l)-{{l-1} \over n}, \mathscr{P}(l)+{1\over n}]$$
But as noted above, the maximum value of $l$ is $O(\log n)$, so both ends of that range are asymptotically $\mathscr{P}(l)$.
In other words, the "fix the dice" strategy does not significantly change the probability that a random node is at a given level. Therefore, it does not "totally destroy" (or even affect) our ability to analyse the algorithms, and there is no reason why even a purist should avoid it.
The strategy demotes (reduces the level) of a newly-created item to one more than the current maximum level in the skip list, if the random level assignment would have produced a higher level. Let's call such an item a demoted item.
Observe that the skip list cannot contain two demoted items at the same level. One of them would have to have been created first, and that would prevent the other one from having been demoted to that level. (Items are never demoted after they are created, so even if deletions entirely empty some level, higher-level items continue to have the same level. One could imagine a strategy which also demoted existing items in such a case, but even then it would be impossible to have two demoted items at the same level.)
The level of an item is limited to $MaxLevel$ (using Pugh's terminology), which means that there are at most $MaxLevel$ demoted items in the skip list. Pugh suggests choosing $MaxLevel$ as $log_{p^{-1}}N$ where $N$ is the expected maximum number of elements in the skip list. In practice, we might use a fixed constant, or we might use $log_{p^{-1}}M$ where $M$ is the maximum size that the skip list has ever reached (assuming we use an implementation where $MaxLevel$ can be incremented). In any case, we expect that $MaxLevel$ is $O(\log n)$.
Now, let's say that $\mathscr{E}(l)$ is the expected number of items at level $l$ without die-fixing and $\mathscr{E}'(l)$ is the expected number in the die-fixed skip list. Die-fixing could cause at most $l-1$ items at level $l$ to be demoted to another level (because there are only $l-1$ lower levels, each of which can have at most one demoted item) and it could cause at most $1$ item at a higher level to be demoted to $l$. So:
$$\mathscr{E}'(l) \in [\mathscr{E}(l)-l-1, \mathscr{E}(l)+1]$$
Since $\mathscr{E}(l) = n\mathscr{P}(l)$, where $\mathscr{P}(l)$ is the probability for a random item to be at level l (analogue $\mathscr{P}'(l)$ for the die-fixed list), we can estimate
$$\mathscr{P}'(l) \in [\mathscr{P}(l)-{{l-1} \over n}, \mathscr{P}(l)+{1\over n}]$$
But as noted above, the maximum value of $l$ is $O(\log n)$, so both ends of that range are asymptotically $\mathscr{P}(l)$.
In other words, the "fix the dice" strategy does not significantly change the probability that a random node is at a given level. Therefore, it does not "totally destroy" (or even affect) our ability to analyse the algorithms, and there is no reason why even a purist should avoid it.
Context
StackExchange Computer Science Q#75691, answer score: 4
Revisions (0)
No revisions yet.