Static Optimality and Dynamic Search Optimality in Lists and TreesList Update ProblemSlide 3Binary Search TreeHow good is a reordering algorithm?Known results..Our results..Revisiting Experts Algorithm [Littlestone Warmuth ’94]Experts for List UpdateCandidate algorithmIdea #2: List Factoring [Borodin ElYaniv]Algorithm for two element listEfficient Experts algorithm for List UpdateCombining Static & Dynamic optimalityHow to estimate weights?Binary Search TreesOutline of our approachAn observation about offline BSTsSlide 19Probability distribution on accessesWhat next?Shuchi Chawla, Carnegie Mellon UniversityStatic Optimalityand Dynamic Search Optimalityin Lists and TreesAvrim BlumShuchi ChawlaAdam Kalai1/6/2002Shuchi Chawla, Carnegie Mellon UniversityList Update ProblemUnordered listAccess for xi takes i time4 7 2 9 12 3 6 8Query for element 9=No=No=No=YesShuchi Chawla, Carnegie Mellon UniversityList Update ProblemUnordered listAccess for xi takes i time9 4 7 2 12 3 6 8Query for element 9Moving up accessed item is FREE!Other reorderings cost 1 per transpositionGoal: minimize total costWhat should the reordering policy be?Shuchi Chawla, Carnegie Mellon UniversityBinary Search Tree“In-order” treeSearch cost = depth of elementCost of rotations = 1 per rotationReplacement policy = ?72 129 141554Shuchi Chawla, Carnegie Mellon UniversityHow good is a reordering algorithm?Compare against the best “offline” algorithmDynamic competitive ratioBest offline algorithm that cannot change state of the list/tree -- “static”Static competitive ratioShuchi Chawla, Carnegie Mellon UniversityKnown results..List updateDynamic ratio [Albers et al’95, Teia’93] : u.b.- 1.6; l.b.- 1.5TreesSplay trees [Sleator Tarjan 85] : static ratio ~ 3No known result on dynamic ratioClassic Machine Learning resultsExperts analysis [LW’94]: static ratio (1+ )Computationally inefficientRecent new result [Kalai Vempala’01] Efficient alg for Strong Static Optimality for treesShuchi Chawla, Carnegie Mellon UniversityOur results..List Update (1+ ) static ratio – efficient variant of ExpertsWe call this “Strong” static optimalityCombining strong static optimality and dynamic optimality to get best of bothSearch treesConstant Dynamic ratio for trees-Given free rotations-ignoring computation timeShuchi Chawla, Carnegie Mellon UniversityRevisiting Experts Algorithm [Littlestone Warmuth ’94]N “expert” algorithmsWe want to be (1+) wrt the best algorithmWeighted Majority algorithmAssign weights to each expert by how well it performsPick probabilistically according to weightsCost incurred < (1+)m + ln(N)/(1-)Applying this to list updateEach list configuration is an expertToo many experts – n!Can we reduce computation?Shuchi Chawla, Carnegie Mellon UniversityExperts for List UpdateWeight for every static list – too much computationThe BIG ideaAssign weights to every item in list and still make an experts style analysis work!Shuchi Chawla, Carnegie Mellon UniversityCandidate algorithmInitialize wi for item iIf ith element accessed, update wiOrder elements using some rule based on wiNeed to analyze probability of getting a particular static listShuchi Chawla, Carnegie Mellon UniversityIdea #2: List Factoring[Borodin ElYaniv]Distribute cost of accessing among pairs of elementsObservation:The relative order of x and y in the list does not depend upon accesses to othersImplication:Only need to analyze a two element list!Shuchi Chawla, Carnegie Mellon UniversityAlgorithm for two element listList – (x,y)Experts – (x,y) and (y,x)weights – wx, wy – correspond to the respective experts!Algorithm:1. Initialize wx, wy to rx & ry R [1..1/]2. If x accessed, wx <- wx+1 else wy <- wy+13. Always keep the element with higher weight in frontShuchi Chawla, Carnegie Mellon UniversityEfficient Experts algorithm for List UpdateSelect ri R [1..1/] for element iInitialize wi <- riIf ith element accessed, wi <- wi+1Order elements in decreasing order of weight(1+) static competitive[Kalai Vempala’01] give a similar result for treesShuchi Chawla, Carnegie Mellon UniversityCombining Static & Dynamic optimalityA has strong static optimality, B has dynamic optimalityCombine the two to get the best of bothApply Experts againTechnical difficultiesCannot estimate weights – running both simultaneously defeats our purposeExperts maintain state - Huge cost of switchingDon’t switch very oftenShuchi Chawla, Carnegie Mellon UniversityHow to estimate weights?The Bandits approach [Burch 00]Bandit can sample at most one slot machine at a timeRun the (so far) better expertAssume good behavior from the other- Pessimistic approachAfter a few runs, we have sampled each one sufficientlyDetails in the paperShuchi Chawla, Carnegie Mellon UniversityBinary Search TreesSplay trees achieve constant static ratioNo results on dynamic optimalitySimplifying the problem…Allow free rotationsAllow unlimited computationWe give a constant dynamic ratioShuchi Chawla, Carnegie Mellon UniversityOutline of our approachDesign a probability distribution p over accesses:Low offline cost => greater probabilityAssume p reflects reality and predict the next access from it.Construct tree based on conditional probability of next accessLow offline cost => node closer to root => low online costShuchi Chawla, Carnegie Mellon UniversityAn observation about offline BSTsAn access sequence with offline cost k can be expressed in 12k bitsAt most 212k sequences of offline cost k.Shuchi Chawla, Carnegie Mellon UniversityAn observation about offline BSTsAn access sequence with offline cost k can be expressed in 12k bitsExpress access sequence as rotations performed by an offline algorithmStart with a fixed tree, make some assumptions about offline algorithm – gives extra factor of 2Express rotations from one tree to another using 6 bits per rotationAt most 212k sequences of offline cost k.Shuchi Chawla, Carnegie Mellon UniversityProbability distribution on accesses Distribution on access sequence a :p(a) > 2-13k where k = offline cost of aUse this to calculate conditional probability of next accessConstruct tree such that Cost of accessing =  ln(1/p(a))= O(k)Shuchi Chawla,