Lecture 6/8: Esoteric Data Structures


June 8, 2020

πŸ“‚Associated files

Esoteric Data Structures: Skip Lists and Bloom Filters

CS 106B: Programming Abstractions

Spring 2020, Stanford University Computer Science Department

Lecturers: Chris Gregg and Julie Zelenski

A skip list and a bloom filter (to be described in this lecture)


Slide 2

Announcements


Slide 3

Today's Topics


Slide 4

Esoteric Data Structures

A list of esoteric data structures: difference-list, table, 2-3-heap, b-tree, rolling-hash, heightmap, skip-list, kd-tree, lookup, splay-tree


Slide 5

Skip Lists


Slide 6

Improving the Linked List

  • log(n)?
    • Nope!
  • It is O(n) – we must traverse the list!


Slide 7

Improving the Linked List


Slide 8

Improving the Linked List

  • These are subway stops on the NYC 7th Avenue line!


Slide 9

Skip Lists

  L1: 14←--β†’34⇔42←---------β†’72
      ⇕     ⇕  ⇕            ⇕
  L2: 14⇔23⇔34⇔42⇔50⇔59⇔66⇔72⇔79

Slide 10

Skip Lists


Slide 11

Skip Lists


Slide 12

Building a Skip List


Slide 13

Bloom Filters


Slide 14

Bloom Filters

1 0 1 1 0 1 1 1
0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0

Slide 15

Bloom Filter Example Insertions

0 1 2 3 4 5 6 7
0 0 0 1 0 0 1 0
0 1 2 3 4 5 6 7
0 0 0 1 0 0 1 1

Slide 16

Bloom Filters: Determining if a value is in the set


Slide 17

Bloom Filters: Probability of a False Positive


Slide 18

Bloom Filters: Why?