ALCOMFT-TR-01-153

Funda Ergun, S. Cenk Sahinalp, Jonathan Sharp and Rakesh K. Sinha
Biased Dictionaries with Fast Insert/Deletes
Warwick. Work package 4. June 2001.

Abstract: A dictionary data structure supports efficient search, insert, and delete operations on n keys from a totally ordered universe. Red-black trees, 2-3 trees, AVL trees, skip lists and other classic data structures facilitate O(log n) time search, insert and deletes, matching the information theoretic lower bound when access probabilities are uniform i.i.d. If access probabilities are non-uniform but still i.i.d., there are other weighted data structures such as D-trees, biased search trees, splay trees and treaps which can achieve optimality.

In many applications, however, the source of non-uniformity in access probabilities is locality of reference: examples include memory, cache, disk and buffer management and emerging applications in internetwork traffic management. In such applications, the access probability of any given key is not i.i.d., but decreases with idle time since the last access to the key.

It is possible to adjust the weighted dictionaries to achieve optimal search time even under time dependent distributions; however insert/delete times will be suboptimal at O(log n). In this paper, we present a lazy updating scheme which can be applied to weighted dictionaries to improve their amortized insert/delete performance when access probabilities decrease with time; optimality of search time is preserved. More specifically, let r(k) be the number of distinct keys accessed since the last access to key k - that is r(k) is the move-to-front rank of k. Let r_max(k) be the maximum rank of k during its lifetime. Then our lazy update scheme enables the abovementioned data structures to perform search in O(log r(k)) time and insert/delete in O(log r_max(k)) time. We illustrate our lazy update scheme in the context of a new Biased Skip List data structure and show that our bounds are optimal.

Postscript file: ALCOMFT-TR-01-153.ps.gz (129 kb).