Lecture 4: Divide and Conquer: Van Emde Boas Trees

Lecture 4: Divide and Conquer: van Emde Boas Trees • Series of Improved Data Structures • Insert, Successor • Delete • Space This lecture is based on personal communication with Michael Bender, 2001. Goal We want to maintain n elements in the range {0, 1, 2, . . . , u − 1} and perform Insert, Delete and Successor operations in O(log log u) time. • If n = nO(1) or n(log n) O(1) , then we have O(log log n) time operations – Exponentially faster than Balanced Binary Search Trees – Cooler queries than hashing • Application: Network Routing Tables – u = Range of IP Addresses → port to send (u = 232 in IPv4) Where might the O(log log u) bound arise ? • Binary search over O(log u) elements • Recurrences log u – T (log u) = T + O(1) 2 √ – T (u) = T ( u) + O(1) Improvements We will develop the van Emde Boas data structure by a series of improvements on a very simple data structure. 1 Bit Vector We maintain a vector V of size u such that V [ x ] = 1 if and only if x is in the set. Now, inserts and deletes can be performed by just flipping the corresponding bit in the vector. However, successor/predecessor requires us to traverse through the vector to find the next 1-bit. • Insert/Delete: O(1) • Successor/Predecessor: O(u) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 Figure 1: Bit vector for u = 16. THe current set is {1, 9, 10, 15}. Split Universe into Clusters We can improve performance by splitting up the range {0, 1, 2, . . . , u − 1} into √ √ clusters of size u. If x = i u + j, then V [ x ] = V.Cluster [i ][ j]. √ low( x ) = x mod u = j x =i high( x ) = √ u √ index (i, j) = i u + j √ u 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 V.Cluster [0] V.Cluster [1] V.Cluster [2] Figure 2: Bit vector (u = 16) split into √ V.Cluster [3] 16 = 4 clusters of size 4. • Insert: – Set V.cluster [ high( x )][low( x )] = 1 2 O(1) – Mark cluster high( x ) as non-empty O(1) • Successor: √ O( u) √ O( u) √ O( u) √ Total = O( u) – Look within cluster high( x ) – Else, find next non-empty cluster i – Find minimum entry j in that cluster – Return index (i, j) Recurse The three operations in Successor are also Successor calls to vectors of size can use recursion to speed things up. √ √ • V.cluster [i ] is a size- u van Emde Boas structure (∀ 0 ≤ i < u) √ • V.summary is a size- u van Emde Boas structure • V.summary[i ] indicates whether V.cluster [i ] is nonempty I NSERT (V, x ) 1 2 Insert(V.cluster [ high( x )], low[ x ]) Insert(V.summary, high[ x ]) So, we get the recurrence: √ T (u) = 2T ( u) + O(1) T ' (log u) = 2T ' log u 2 + O(1) =⇒ T (u) = T ' (log u) = O(log u) S UCCESSOR (V, x ) 1 i = high( x ) 2 j = Successor (V.cluster [i ], j) 3 if j == ∞ 4 i = Successor (V.summary, i ) 5 j = Successor (V.cluster [i ], −∞) 6 return index (i, j) 3 √ u. We √ T (u) = 3T ( u) + O(1)   ' ' log u + O(1) T (log u) = 3T 2 =⇒ T (u) = T ' (log u) = O((log u)log 3 ) ≈ O((log u)1.585 ) To obtain the O(log log u) running time, we need to reduce the number of re­ cursions to one. Maintain Min and Max We store the minimum and maximum entry in each structure. This gives an O(1) time overhead for each Insert operation. S UCCESSOR (V, x ) 1 i = high( x ) 2 if low( x ) < V.cluster [i ].max 3 j = Successor (V.cluster [i ], low( x )) 4 else i = Successor (V.summary, high( x )) 5 j = V.cluster [i ].min 6 return index (i, j) √ T (u) = T ( u) + O(1) =⇒ T (u) = O(log log u) Don’t store Min recursively The Successor call now needs to check for the min separately. if x < V.min : return V.min 4 (1) I NSERT (V, x ) 1 2 3 4 5 6 7 8 9 10 if V.min == None V.min = V.max = x I O(1) time return if x < V.min swap( x ↔ V.min) if x > V.max V.max = x) if V.cluster [ high( x ) == None Insert(V.summary, high( x )) I First Call Insert(V.cluster [ high( x )], low( x )) I Second Call If the first call is executed, the second call only takes O(1) time. So √ T (u) = T ( u) + O(1) =⇒ T (u) = O(log log u) D ELETE (V, x ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 if x == V.min I Find new min i = V.summary.min if i = None V.min = V.max = None I O(1) time return V.min = index (i, V.cluster [i ].min) I Unstore new min Delete(V.cluster [ high( x )], low( x )) I First Call if V.cluster [ high( x )].min == None Delete(V.summary, high( x )) I Second Call I Now we update V.max if x == V.max if V.summary.max = None else i = V.summary.max V.max = index (i, V.cluster [i ].max ) If the second call is executed, the first call only takes O(1) time. So √ T (u) = T ( u) + O(1) =⇒ T (u) = O(log log u) 5 Lower Bound [Patrascu & Thorup 2007] Even for static queries (no Insert/Delete) • Ω(log log u) time per query for u = n(log n) O(1) • O(n · poly(log n)) space Space Improvements We can improve from Θ(u) to O(n log log u). • Only create nonempty clusters – If V.min becomes None, deallocate V • Store V.cluster as a hashtable of nonempty clusters • Each insert may create a new structure Θ(log log u) times (each empty insert) ˇ at] – Can actually happen [Vladimir Cun´ • Charge pointer to structure (and associated hash table entry) to the structure This gives us O(n log log u) space (but randomized). Indirection We can further reduce to O(n) space. • Store vEB structure with n = O(log log u) using BST or even an array =⇒ O(log log n) time once in base case • We use O(n/ log log u) such structures (disjoint) n =⇒ O( log log u · log log u ) = O( n ) space for small • Larger structures “store” pointers to them n =⇒ O( log log u · log log u ) = O( n ) space for large • Details: Split/Merge small structures 6