14 Skip Lists

1. Analysis of Algorithms Skip Lists Andres Mendez-Vazquez October 18, 2015 1 / 99

2. Outline 1 Dictionaries Deﬁnitions Dictionary operations Dictionary implementation 2 Skip Lists Why Skip Lists? The Idea Behind All of It!!! Skip List Deﬁnition Skip list implementation Insertion for Skip Lists Deletion in Skip Lists Properties Search and Insertion Times Applications Summary 2 / 99

4. Dictionaries Deﬁnition A dictionary is a collection of elements; each of which has a unique search key. Uniqueness criteria may be relaxed (multi-set). Do not force uniqueness. Purpose Dictionaries keep track of current members, with periodic insertions and deletions into the set (similar to a database). Examples Membership in a club. Course records. Symbol table (with duplicates). Language dictionary (Webster, RAE, Oxford). 4 / 99

12. Example: Course records Dictionary with member records key ID Student Name HW1 123 Stan Smith 49 · · · 125 Sue Margolin 45 · · · 128 Billie King 24 · · · ... ... 190 Roy Miller 36 · · · 5 / 99

14. The dictionary ADT operations Some operations on dictionaries size(): Returns the size of the dictionary. empty(): Returns TRUE if the dictionary is empty. findItem(key): Locates the item with the specified key. findAllItems(key): Locates all items with the specified key. removeItem(key): Removes the item with the specified key. removeAllItems(key): Removes all items with the specified key. insertItem(key,element): Inserts a new key-element pair. 7 / 99

21. Example of unordered dictionary Example Consider an empty unordered dictionary, we have then... Operation Dictionary Output InsertItem(5, A) {(5, A)} InsertItem(7, B) {(5, A) , (7, B)} findItem(7) {(5, A) , (7, B)} B findItem(4) {(5, A) , (7, B)} No Such Key size() {(5, A) , (7, B)} 2 removeItem(5) {(7, B)} A findItem(4) {(7, B)} No Such Key 8 / 99

23. How to implement a dictionary? There are many ways of implementing a dictionary Sequences / Arrays Ordered Unordered Binary search trees Skip lists Hash tables 10 / 99

27. Recall Arrays... Unordered array Complexity Searching and removing takes O(n). Inserting takes O(1). Applications This approach is good for log ﬁles where insertions are frequent but searches and removals are rare. 11 / 99

31. More Arrays Ordered array Complexity Searching takes O(log n) time (binary search). Insert and removing takes O(n) time. Applications This aproach is good for look-up tables where searches are frequent but insertions and removals are rare. 12 / 99

35. Binary searches Features Narrow down the search range in stages “High-low” game. 13 / 99

36. Binary searches Example ﬁnd Element(22) 2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 ↑ LOW ↑ MID ↑ HIGH 2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 ↑ LOW ↑ MID ↑ HIGH 2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 ↑ LOW ↑ MID ↑ HIGH 2 4 5 7 8 9 12 14 17 19 22 25 27 28 33 ↑ LOW=MID=HIGH 14 / 99

40. Recall binary search trees Implement a dictionary with a BST A binary search tree is a binary tree T such that: Each internal node stores an item (k, e) of a dictionary. Keys stored at nodes in the left subtree of v are less than or equal to k. Keys stored at nodes in the right subtree of v are greater than or equal to k. 15 / 99

44. Binary searches Trees Problem!!! Keeping a Well Balanced Binary Search Tree can be diﬃcult!!! 44 17 88 65 54 82 76 80 32 28 29 97 16 / 99

45. Not only that... Binary Search Trees They are not so well suited for parallel environments. Unless a heavy modiﬁcations are done In addition We want to have a Compact Data Structure. Using as little memory as possible 17 / 99

49. Thus, we have the following possibilities Unordered array complexities Insertion: O(1) Search: O(n) Ordered array complexities Insertion: O(n) Search: O(n log n) Well balanced binary trees complexities Insertion: O(log n) Search: O(log n) Big Drawback - Complex parallel Implementation and waste of memory. 18 / 99

52. We want something better!!! For this We will present a probabilistic data structure known as Skip List!!! 19 / 99

54. Starting from Scratch First Imagine that you only require to have searches. A ﬁrst approximation to it is the use of a link list for it (Θ(n) search complexity). Then, using this How do we speed up searches? Something Notable Use two link list, one a subsequence of the other. Imagine the two lists as a road system 1 The Bottom is the normal road system, L2. 2 The Top is the high way system, L1. 21 / 99

61. Example High-Bottom Way System 14 14 23 34 42 47 63 34 42 23 / 99

62. Thus, we have... The following rule To Search ﬁrst search in the top one (L1) as far as possible, then go down and search in the bottom one (L2). 24 / 99

63. We can use a little bit of optimization We have the following worst cost Search Cost High-Bottom Way System = Cost Searching Top +... Cost Search Bottom Or Search Cost =length (L1) + Cost Search Bottom The interesting part is “Cost Search Bottom” This can be calculated by the following quotient: length (L2) length (L1) 25 / 99

64. We can use a little bit of optimization We have the following worst cost Search Cost High-Bottom Way System = Cost Searching Top +... Cost Search Bottom Or Search Cost =length (L1) + Cost Search Bottom The interesting part is “Cost Search Bottom” This can be calculated by the following quotient: length (L2) length (L1) 25 / 99

65. Why? If we think we are jumping Segment 1 Segment 2 14 14 23 34 34 26 30 26 Then cost of searching each of the bottom segments = 2 Thus the ratio is a “decent” approximation to the worst case search length (L2) length (L1) = 5 3 = 1.66 26 / 99

66. Why? If we think we are jumping Segment 1 Segment 2 14 14 23 34 34 26 30 26 Then cost of searching each of the bottom segments = 2 Thus the ratio is a “decent” approximation to the worst case search length (L2) length (L1) = 5 3 = 1.66 26 / 99

67. Thus, we have... Then, the cost for a search (when length (L2) = n) Search Cost = length (L1)+ length (L2) length (L1) = length (L1)+ n length (L1) (1) Taking the derivative with respect to length (L1) and making the result equal 0 1 − n length2 (L1) = 0 27 / 99

68. Thus, we have... Then, the cost for a search (when length (L2) = n) Search Cost = length (L1)+ length (L2) length (L1) = length (L1)+ n length (L1) (1) Taking the derivative with respect to length (L1) and making the result equal 0 1 − n length2 (L1) = 0 27 / 99

69. Final Cost We have that the optimal length for L1 length (L1) = √ n Plugging back in (Eq. 1) Search Cost = √ n + n √ n = √ n + √ n = 2 × √ n 28 / 99

70. Final Cost We have that the optimal length for L1 length (L1) = √ n Plugging back in (Eq. 1) Search Cost = √ n + n √ n = √ n + √ n = 2 × √ n 28 / 99

71. Data structure with a Square Root Relation Something like this 29 / 99

72. Now For a three layer link list data structure We get a search cost of 3 × 3 √ n In general for k layers, we have k × k √ n Thus, if we make k = log2 n, we get Search Cost = log2 n × log2 n √ n = log2 n × (n) 1/log2 n = log2 n × (n)logn 2 = log2 n × 2 =Θ (log2 n) 30 / 99

75. Thus Something Notable We get the advantages of the binary search trees with a simpler architecture!!! 31 / 99

76. Thus Binary Search Trees 44 17 88 65 54 82 76 80 32 28 29 97 New Architecture 32 / 99

77. Thus Binary Search Trees 44 17 88 65 54 82 76 80 32 28 29 97 New Architecture 14 14 23 34 42 47 63 34 42 32 / 99

78. Now We are ready to give a Deﬁnition for Skip List 33 / 99

80. A Little Bit of History Skip List They were invented by William Worthington "Bill" Pugh Jr.!!! How is him? He is is an American computer scientist who invented the skip list and the Omega test for deciding Presburger arithmetic. He was the co-author of the static code analysis tool FindBugs. He was highly inﬂuential in the development of the current memory model of the Java language together with his PhD student Jeremy Manson. 35 / 99

84. Skip List Deﬁnition Deﬁnition A skip list for a set S of distinct (key,element) items is a series of lists S0, S1, ..., Sh such that: Each list Si contains the special keys +∞ and −∞ List S0 contains the keys of S in nondecreasing order Each list is a subsequence of the previous one S0 ⊇ S1 ⊇ S2 ⊇ ... ⊇ Sh List Sh contains only the two special keys 36 / 99

90. Skip List Deﬁnition Example 12 23 23 26 31 31 31 34- - - - + + + + 34 44 56 64 64 78 37 / 99

91. Skip list search We search for a key x in a skip list as follows We start at the ﬁrst position of the top list. At the current position p, we compare x with y == p.next.key x == y: we return p.next.element x > y: we scan forward x < y: we “drop down” If we try to drop down past the bottom list, we return null. 38 / 99

97. Example search for 78 x < p.next.key: “drop down” 12 23 23 26 31 31 31 34- - - - + + + + 34 44 56 64 64 78 p 39 / 99

98. Example search for 78 x > p.next.key: “scan forward” 12 23 23 26 31 31 31 34- - - - + + + + 34 44 56 64 64 78 p 40 / 99

103. Example search for 78 x == y: we return p.next.element 12 23 23 26 31 31 31 34- - - - + + + + 34 44 56 64 64 78 p 45 / 99

105. How do we implement this data structure? We can implement a skip list with quad-nodes A quad-node stores: Entry Value Link to the previous node Link to the next node Link to the above node Link to the below node Also we deﬁne special keys PLUS_INF and MINUS_INF, and we modify the key comparator to handle them. 47 / 99

112. Example Quad-Node Example 48 / 99

113. Skip lists uses Randomization Use of randomization We use a randomized algorithm to insert items into a skip list. Running time We analyze the expected running time of a randomized algorithm under the following assumptions: The coins are unbiased. The coin tosses are independent. Worst case running time The worst case running time of a randomized algorithm is often large but has very low probability. e.g. It occurs when all the coin tosses give “heads.” 49 / 99

120. Insertion To insert To insert an entry (key, object) into a skip list, we use a randomized algorithm: We repeatedly toss a coin until we get tails: We denote with i the number of times the coin came up heads. If i ≥ h, we add to the skip list new lists Sh+1, ..., Si+1: Each containing only the two special keys. We search for x in the skip list and ﬁnd the positions p0, p1, ..., pi of the items with largest key less than x in each lists S0, S1, ..., Si. For j ← 0, ..., i, we insert item (key, object) into list Sj after position pj. 51 / 99

128. Example: Insertion of 15 in the skip list First, we use i = 2 to insert S3 into the skip list - - - 12 23 23 26 + + + - - - 12 23 23 26 + + + - +- + 52 / 99

129. Example: Insertion of 15 in the skip list Clearly, you ﬁrst search for the predecessor key!!! - - - 12 23 23 26 + + + - - - 12 23 23 26 + + + - +- + 53 / 99

130. Example: Insertion of 15 in the skip list Insert the necessary Quad-Nodes and necessary information - - - 12 23 23 26 + + + - + pred 54 / 99

131. Example: Insertion of 15 in the skip list Insert the necessary Quad-Nodes and necessary information - - - 12 23 23 26 + + + - + pred 15 55 / 99

132. Example: Insertion of 15 in the skip list Insert the necessary Quad-Nodes and necessary information - - - 12 23 23 26 + + + - + pred 15 15 56 / 99

133. Example: Insertion of 15 in the skip list Finally!!! - - - 12 23 23 26 + + + - + 15 15 15 57 / 99

135. Deletion To remove an entry with key x from a skip list, we proceed as follows We search for x in the skip list and ﬁnd the positions p0, p1, ..., pi of the items with key x, where position pj is in list Sj. We remove positions p0, p1, ..., pi from the lists S0, S1, ..., Si. We remove all but one list containing only the two special keys 59 / 99

138. Example: Delete of 34 in the skip list We search for 34 in the skip list and ﬁnd the positions p0, p1, ..., p2 of the items with key 34 - - - 12 - 23 23 45 + + + + 34 34 34 60 / 99

139. Example: Delete of 34 in the skip list We search for 34 in the skip list and ﬁnd the positions p0, p1, ..., p2 of the items with key 34 - - - 12 - 23 23 45 + + + + 34 34 34 61 / 99

140. Example: Delete of 34 in the skip list We start doing the deletion!!! - - - 12 - 23 23 45 + + + + 34 34 34 62 / 99

141. Example: Delete of 34 in the skip list One Quad-Node after another - - - 12 - 23 23 45 + + + + 34 34 63 / 99

142. Example: Delete of 34 in the skip list One Quad-Node after another - - - 12 - 23 23 45 + + + + 34 64 / 99

143. Example: Delete of 34 in the skip list One Quad-Node after another - - - 12 - 23 23 45 + + + + 65 / 99

144. Example: Delete of 34 in the skip list Remove One Level - - - 12 23 23 45 + + + 66 / 99

146. Space usage Space usage The space used by a skip list depends on the random bits used by each invocation of the insertion algorithm. 68 / 99

147. Space : O (n) Theorem The expected space usage of a skip list with n items is O(n). Proof We use the following two basic probabilistic facts: 1 Fact 1: The probability of getting i consecutive heads when ﬂipping a coin is 1 2i . 2 Fact 2: If each of n entries is present in a set with probability p, the expected size of the set is np. 1 How? Remember X = X1 + X2 + ... + Xn where Xi is an indicator function for event Ai = the i element is present in the set. Thus: E [X] = n i=1 E [Xi] = n i=1 Pr {Ai} Equivalence E[XA] and Pr{A} = n i=1 p = np 69 / 99

153. Proof Now consider a skip list with n entries Using Fact 1, an element is inserted in list Si with a probability of 1 2i Now by Fact 2 The expected size of list Si is n 2i 70 / 99

154. Proof Now consider a skip list with n entries Using Fact 1, an element is inserted in list Si with a probability of 1 2i Now by Fact 2 The expected size of list Si is n 2i 70 / 99

155. Proof The expected number of nodes used by the skip list with height h h i=0 n 2i = n h i=0 1 2i Here, we have a problem!!! What is the value of h? 71 / 99

156. Height h First The running time of the search and insertion algorithms is aﬀected by the height h of the skip list. Second We show that with high probability, a skip list with n items has height O(log n). 72 / 99

157. Height h First The running time of the search and insertion algorithms is aﬀected by the height h of the skip list. Second We show that with high probability, a skip list with n items has height O(log n). 72 / 99

158. For this, we have the following fact!!! We use the following Fact 3 We can view the level l (xi) = max {j|where xi ∈ Sj} of the elements in the skip list as the following random variable Xi = l (xi) for each element xi in the skip list. And this is a random variable!!! Remember the insertions!!! Using an unbiased coin!! Thus, all Xi have a geometric distribution. 73 / 99

161. Example for l (xi) We have - - - 12 - 23 23 45 + + + + 34 34 34 1 2 3 1 74 / 99

162. BTW What is the geometric distribution? k failures where k = {1, 2, 3, ...} Probability mass function Pr (X = k) = (1 − p)k−1 p 75 / 99

163. BTW What is the geometric distribution? k failures where k = {1, 2, 3, ...} Probability mass function Pr (X = k) = (1 − p)k−1 p 75 / 99

164. Probability Mass Function For Diﬀerent Probabilities 76 / 99

165. Then We have the following inequality for the geometric variables Pr [Xi > t] ≤ (1 − p)t ∀i = 1, 2, ..., n Because if the cdf F (t) = P (X ≤ t) = 1 − (1 − p)t+1 Then, we have Pr max i Xi > t ≤ n(1 − p)t This comes from Fmaxi Xi (t) = (F (t))n 77 / 99

166. Then We have the following inequality for the geometric variables Pr [Xi > t] ≤ (1 − p)t ∀i = 1, 2, ..., n Because if the cdf F (t) = P (X ≤ t) = 1 − (1 − p)t+1 Then, we have Pr max i Xi > t ≤ n(1 − p)t This comes from Fmaxi Xi (t) = (F (t))n 77 / 99

167. Observations The maxi Xi It represents the list with the one entry apart from the special keys. - - - 12 - 23 23 45 + + + + 34 34 34 78 / 99

168. Observations REMEMBER!!! We are talking about a fair coin, thus p = 1 2. 79 / 99

169. Height: 3 log2 n with probability at least 1 − 1 n2 Theorem A skip list with n entries has height at most 3 log2 n with probability at least 1 − 1 n2 80 / 99

170. Proof Consider a skip list with n entires By Fact 3, the probability that list St has at least one item is at most n 2t . P (|St| ≥ 1) = P max i Xi > t = n 2t . By picking t = 3 log n We have that the probability that S3 log2 n has at least one entry is at most: n 23 log2 n = n n3 = 1 n2 . 81 / 99

171. Proof Consider a skip list with n entires By Fact 3, the probability that list St has at least one item is at most n 2t . P (|St| ≥ 1) = P max i Xi > t = n 2t . By picking t = 3 log n We have that the probability that S3 log2 n has at least one entry is at most: n 23 log2 n = n n3 = 1 n2 . 81 / 99

172. Look at we want to model We want to model The height of the Skip List is at most t = 3 log2 n Equivalent to the negation of having list S3 log2 n Then, the probability that the height h = 3 log2 n of the skip list is P (Skip List height 3 log2 n) = 1 − 1 n2 82 / 99

175. Finally The expected number of nodes used by the skip list with height h Given that h = 3 log2 n 3 log2 n i=0 n 2i = n 3 log2 n i=0 1 2i Given the geometric sum Sm = m k=0 rk = 1 − rm+1 1 − r 83 / 99

176. Finally The expected number of nodes used by the skip list with height h Given that h = 3 log2 n 3 log2 n i=0 n 2i = n 3 log2 n i=0 1 2i Given the geometric sum Sm = m k=0 rk = 1 − rm+1 1 − r 83 / 99

177. We have ﬁnally The Upper Bound on the number of nodes n 3 log2 n i=0 1 2i =n 1 − (1/2)3 log2 n+1 1 − 1/2 =n 1 − 1/2 (1/2log2 n)3 1/2 We have then 1 2log2 n = 1 n Then n 1 − 1/2 (1/2log2 n)3 1/2 = n 1 − 1 2n2 1/2 = n 2 − 1 2n2 = 2n − 1 2n 84 / 99

180. Finally The Upper Bound with probability 1 − 1 n2 2n − 1 2n ≤ 2n = O (n) 85 / 99

182. Search and Insertion Times Something Notable The expected number of coin tosses required in order to get tails is 2. We use this To prove that a search in a skip list takes O(log n) expected time. After all insertions require searches!!! 87 / 99

183. Search and Insertion Times Something Notable The expected number of coin tosses required in order to get tails is 2. We use this To prove that a search in a skip list takes O(log n) expected time. After all insertions require searches!!! 87 / 99

184. Search and Insertions times Search time The search time in skip list is proportional to the number of drop-down steps + the number of scan-forward steps Drop-down steps The drop-down steps are bounded by the height of the skip list and thus are O (log2 n) with high probability. Theorem A search in a skip list takes O (log2 n) expected time. 88 / 99

187. Proof First When we scan forward in a list, the destination key does not belong to a higher list. A scan-forward step is associated with a former coin toss that gave tails By Fact 4, in each list the expected number of scan-forward steps is 2. 89 / 99

188. Proof First When we scan forward in a list, the destination key does not belong to a higher list. A scan-forward step is associated with a former coin toss that gave tails By Fact 4, in each list the expected number of scan-forward steps is 2. 89 / 99

189. Why? Given the list Si Then, the scan-forward intervals (Jumps between xi and xi+1) to the right of Si are I1 = [x1, x2],I2 = [x2, x3]...Ik = [xk, +∞] Then These interval exist at level i if and only if all x1, x2, ..., xk belong to Si. 90 / 99

190. Why? Given the list Si Then, the scan-forward intervals (Jumps between xi and xi+1) to the right of Si are I1 = [x1, x2],I2 = [x2, x3]...Ik = [xk, +∞] Then These interval exist at level i if and only if all x1, x2, ..., xk belong to Si. 90 / 99

191. We introduce the following concept based on these intervals Scan-forward siblings These are element that you ﬁnd in the search path before ﬁnding an element in the upper list. 91 / 99

192. Now Given that a search is being done, Si contains l forward siblings It must be the case that given x1, ..., xl scan-forward siblings, we have that x1, ..., xl /∈ Si+1 and xl+1 ∈ Si+1 92 / 99

193. Thus We have Since each element of Si is independently chosen to be in Si+1 with probability p = 1 2. We have The number of scan-forward siblings is bounded by a geometric random variable Xi with parameter p = 1 2. Thus, we have that The expected number of scan-forward siblings is bounded by 2!!! Expected # Scan-Fordward Siblings at i ≤ E [Xi] = 1 1/2 Mean = 2 93 / 99

196. Then In the worst case scenario A search is bounded by 2 log2 n = O (log2 n) An given that a insertion is a (search) + (deletion bounded by the height) Thus, an insertion is bounded by 2 log2 n + 3 logn n = O (log2 n) 94 / 99

197. Then In the worst case scenario A search is bounded by 2 log2 n = O (log2 n) An given that a insertion is a (search) + (deletion bounded by the height) Thus, an insertion is bounded by 2 log2 n + 3 logn n = O (log2 n) 94 / 99

199. Applications We have Cyrus IMAP servers oﬀer a "skiplist" backend Data Base implementation. Lucene uses skip lists to search delta-encoded posting lists in logarithmic time. Redis, an ANSI-C open-source persistent key/value store for Posix systems, uses skip lists in its implementation of ordered sets. leveldb, a fast key-value storage library written at Google that provides an ordered mapping from string keys to string values. Skip lists are used for eﬃcient statistical computations of running medians. 96 / 99

205. Summary Summary A skip list is a data structure for dictionaries that uses a randomized insertion algorithm. In a skip list with n entries: The expected space used is O(n) The expected search, insertion and deletion time is O(log n) Skip list are fast and simple to implement in practice. 98 / 99

211. Thanks Questions? 99 / 99

14 Skip Lists

Recommended

More Related Content

What's hot (20)

Similar to 14 Skip Lists (20)

More from Andres Mendez-Vazquez (20)

Recently uploaded (20)

14 Skip Lists