An Experimental Study of Dynamic Biased Skip Lists

Abstract

Skip lists allow search, insert, and delete operations in O(log n) average time. However, they show a lack of efficiency when dealing with data exhibiting locality of reference, meaning the keys are searched or updated non-uniformly. The dynamic biased skip list (DBSL) allows O(log r(k)) amortized time per operation, where r(k) is the number of distinct keys accessed after k was last accessed.

The performance of DBSL has not been fully evaluated. We implemented DBSL and compared it with move-to-front lists, red-black trees and splay trees, using real-world and synthetic data. Our results show that when a highly biased data sequence contains delete operations, DBSL is more efficient compared to the others. When the degree of bias is moderate, DBSL is not competitive against splay trees, but is more efficient than red-black trees and skip lists. When the data sequence is less biased, DBSL is the least efficient.