IntroductionRelated Prior WorkOur ResultsBiased Skip ListsUpdating Deterministic Biased SkiplistsInserting an ItemDeleting an ItemJoining Two SkiplistsSplitting a SkiplistFinger SearchingChanging the Weight of an ItemRandomized UpdatesConclusionReferences1Biased Skip ListsAmitabha Bagchi1, Adam L. Buchsbaum2, and Michael T. Goodrich3∗1Dept. of Computer Science, Johns Hopkins Univ., Baltimore, MD 21218,[email protected]&T Labs, Shannon Laboratory, 180 Park Ave., Florham Park, NJ 07932,[email protected]. of Info. & Computer Science, Univ. of California, Irvine, CA 92697-3425,[email protected]. We design a variation of skip lists that performs well forgenerally biased access sequences. Given n items, each with a positiveweight wi,1≤ i ≤ n, the time to access item i is O1 + logWwi, whereW = ni=1wi; the data structure is dynamic. We present deterministicand randomized variations, which are nearly identical; the determinis-tic one simply ensures the balance condition that the randomized oneachieves probabilistically. We use the same method to analyze both.1 IntroductionThe primary goal of data structures research is to design data organizationmechanisms that admit fast access and update operations. For a generic n-element ordered data set that is accessed and updated uniformly, this goal istypically satisfied by dictionaries that achieve O(log n)-time search and updateperformance; e.g., AVL-trees [2], red-black trees [12], and (a, b)-trees [13].Nevertheless, many dictionary applications involve sets of weighted dataitems subject to non-uniform access patterns that are biased according to theweights. For example, operating systems (e.g., see Stallings [22]) deal with bi-asing in memory requests. Other recent examples of biased sets include clientweb server requests [11] and DNS lookups [6]. For such applications, a biasedsearch structure is more appropriate—that is, a structure that achieves searchtimes faster than log n for highly weighted items. Biased searching is also usefulin auxiliary structures deployed inside other data structures [5,10,20].Formally, a biased dictionary is a data structure that maintains an orderedset X, each element i of which has a weight, wi; without loss of generality, weassume wi≥ 1. The operations are as follows.Search(X, i). Determine if i is in X.Insert(X, i). Add i to X.Delete(X, i). Delete i from X.Join(XL,XR). Assuming that i<jfor each i ∈ XLand j ∈ XR, create a newset X = XL∪ XR. The operation destroys XLand XR.Supported by DARPA Grant F30602-00-2-0509 and NSF Grant CCR-0098068.P. Bose and P. Morin (Eds.): ISAAC 2002, LNCS 2518, pp. 1–13, 2002.c Springer-Verlag Berlin Heidelberg 20022 A. Bagchi, A.L. Buchsbaum, and M.T. GoodrichSplit(X, i). Assuming without loss of generality that i ∈ X, create XL= {j ∈X : j<i} and XR= {j ∈ X : j>i}. The operation destroys X.FingerSearch(X, i, j). Determine if j is in X, exploiting a handle in the datastructure to element i ∈ X.Reweight(X, i, w i). Change the weight of i to w i.In this paper, we study efficient data structures for biased data sets subjectto these operations. We desire search times that are asymptotically optimal andupdate times that are also efficient. For example, consider the case when wiisthe number of times item i is accessed. Define W =ni=1wi. A biased dictionarywith OlogWwi search time for the i’th item can perform m searches on n itemsin O(m(1 −ni=1pilog pi)) time, where pi=wim, which is asymptotically opti-mal [1]. We therefore desire OlogWwi search times and similar update times forgeneral biased data (with arbitrary weights). We also seek biased structures thatwould be simple to implement and that do not require major restructuring op-erations, such as tree rotations, to achieve biasing. Tree rotations, in particular,make structures less amenable to augmentation, for such rotations often requirethe complete rebuilding of auxiliary structures stored at the affected nodes.1.1 Related Prior WorkThe study of biased data structures is a classic topic in algorithmics. Early workincludes a dynamic programming method by Knuth [14,15] for constructing astatic biased binary search tree for items weighted by their search frequencies.Subsequent work focuses primarily on achieving asymptotically optimal searchtimes while also admitting efficient updates. Most of the known methods forconstructing dynamic biased data structures use search trees, and they differfrom one another primarily in their degree of complication and whether or nottheir resulting time bounds are amortized, randomized, or worst case.Sleator and Tarjan [21] introduce the theoretically elegant splay trees, whichautomatically adjust themselves to achieve optimal amortized biased accesstimes for access-frequency weights. Splay trees store no balance or weight infor-mation, but they perform many tree rotations after every access, which makesthem less practically efficient than even AVL-trees in many applications [3].These rotations can be particularly deleterious when nodes are augmented withauxiliary structures.Bent, Sleator, and Tarjan [4] and Feigenbaum and Tarjan [9] design biasedsearch trees for arbitrary weights that significantly reduce, but do not eliminate,the number of tree rotations needed. They offer efficient worst-case and amor-tized performance of biased dictionary operations but do so with complicatedimplementations.Seidel and Aragon [19] demonstrate randomized bounds with treaps. Likesplay trees, treaps perform a large number of rotations after every access. Theirdata structure is elegant and efficient in practice, but its performance does notachieve bounds that are efficient in a worst-case or amortized sense.Biased Skip Lists 3Pugh [18] introduces an alternative skip list structure, which efficiently im-plements an unbiased dictionary without using rotations. Skip lists store theitems in series of a linked lists, which are themselves linked together in a leveledfashion. Pugh presents skip lists as a randomized structure that is easily im-plemented and shows that they are empirically faster than fast balanced searchtrees, such as AVL-trees. Search and updates take O(log n) expected time in skiplists, with no rotations or other rebalancing needed for updates. Exploiting therelationship between skip lists and (a, b)-trees, Munro, Papadakis, and Sedgewick[17] show how to implement a deterministic version of skip lists that