0 0 10 views

**Unformatted text preview:**

1 Biased Skip Lists Amitabha Bagchi1 Adam L Buchsbaum2 and Michael T Goodrich3 1 Dept of Computer Science Johns Hopkins Univ Baltimore MD 21218 bagchi cs jhu edu 2 AT T Labs Shannon Laboratory 180 Park Ave Florham Park NJ 07932 alb research att com 3 Dept of Info Computer Science Univ of California Irvine CA 92697 3425 goodrich ics uci edu Abstract We design a variation of skip lists that performs well for generally biased access sequences Given n items each with a positive W weight wi 1 i n the time to access item i is O 1 log w where i n W i 1 wi 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 1 Introduction The primary goal of data structures research is to design data organization mechanisms that admit fast access and update operations For a generic nelement ordered data set that is accessed and updated uniformly this goal is typically satis ed by dictionaries that achieve O log n time search and update performance e g AVL trees 2 red black trees 12 and a b trees 13 Nevertheless many dictionary applications involve sets of weighted data items subject to non uniform access patterns that are biased according to the weights For example operating systems e g see Stallings 22 deal with biasing in memory requests Other recent examples of biased sets include client web server requests 11 and DNS lookups 6 For such applications a biased search structure is more appropriate that is a structure that achieves search times faster than log n for highly weighted items Biased searching is also useful in auxiliary structures deployed inside other data structures 5 10 20 Formally a biased dictionary is a data structure that maintains an ordered set X each element i of which has a weight wi without loss of generality we assume 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 j for each i XL and j XR create a new set X XL XR The operation destroys XL and 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 2002 2 A Bagchi A L Buchsbaum and M T Goodrich Split 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 data structure to element i X Reweight X i wi Change the weight of i to wi In this paper we study e cient data structures for biased data sets subject to these operations We desire search times that are asymptotically optimal and update times that are also e cient For example consider the case when wi is n the number of times item i is accessed De ne W w i 1 i A biased dictionary with O log W wi n search time for the i th item can perform m searches on n items wi pi log pi time where pi m which is asymptotically optiW mal 1 We therefore desire O log w search times and similar update times for i in O m 1 i 1 general biased data with arbitrary weights We also seek biased structures that would be simple to implement and that do not require major restructuring operations such as tree rotations to achieve biasing Tree rotations in particular make structures less amenable to augmentation for such rotations often require the complete rebuilding of auxiliary structures stored at the a ected nodes 1 1 Related Prior Work The study of biased data structures is a classic topic in algorithmics Early work includes a dynamic programming method by Knuth 14 15 for constructing a static biased binary search tree for items weighted by their search frequencies Subsequent work focuses primarily on achieving asymptotically optimal search times while also admitting e cient updates Most of the known methods for constructing dynamic biased data structures use search trees and they di er from one another primarily in their degree of complication and whether or not their resulting time bounds are amortized randomized or worst case Sleator and Tarjan 21 introduce the theoretically elegant splay trees which automatically adjust themselves to achieve optimal amortized biased access times for access frequency weights Splay trees store no balance or weight information but they perform many tree rotations after every access which makes them less practically e cient than even AVL trees in many applications 3 These rotations can be particularly deleterious when nodes are augmented with auxiliary structures Bent Sleator and Tarjan 4 and Feigenbaum and Tarjan 9 design biased search trees for arbitrary weights that signi cantly reduce but do not eliminate the number of tree rotations needed They o er e cient worst case and amortized performance of biased dictionary operations but do so with complicated implementations Seidel and Aragon 19 demonstrate randomized bounds with treaps Like splay trees treaps perform a large number of rotations after every access Their data structure is elegant and e cient in practice but its performance does not achieve bounds that are e cient in a worst case or amortized sense Biased Skip Lists 3 Pugh 18 introduces an alternative skip list structure which e ciently implements an unbiased dictionary without using rotations Skip lists store the items in series of a linked lists which are themselves linked together in a leveled fashion Pugh presents skip lists as a randomized structure that is easily implemented and shows that they are empirically faster than fast balanced search trees such as AVL trees Search and updates take O log n expected time in skip lists with no rotations or other rebalancing needed for updates Exploiting the relationship between skip lists and a b trees Munro Papadakis and Sedgewick 17 show how to implement a deterministic version of skip lists that achieves similar bounds in the worst case using simple promote and demote operations For biased skip lists much less prior work exists Mehlhorn and Na her 16 anticipated biased skip lists but claimed only a partial result and omitted details and analysis Recently Ergun et al 7 8 presented a biased skip list structure that is designed for a specialized notion of biasing in which access to an item i takes O log r i expected time where r i is the number of items accessed since the last time i was