We design a variation of skip lists that performs well for generally biased access sequences. Given n items, each with a positive weight w
i, 1≤ i ≤ n, the time to access item i is O (1 + log W/w
i), where W = Σi=1n
w
i; the data structure is dynamic. We present deterministic and randomized variations, which are nearly identical; the deterministic
one simply ensures the balance condition that the randomized one achieves probabilistically. We use the same method to analyze
both.
Supported by DARPA Grant F30602-00-2-0509 and NSF Grant CCR-0098068.