View Related Documents

Abstract

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≤ in, 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.

Fulltext Preview

Image of the first page of the fulltext document