6.851: Advanced Data Structures (Spring'14)

Prof. Erik Demaine     TAs: Timothy Kaler, Aaron Sidford

[Home] [Lectures] [Assignments] [Project] [Open Problems] [Piazza]

Lecture 8 Video     [previous] [next] [completion form]

[+] Memory hierarchy: ordered-file maintenance, list labeling, order queries, cache-oblivious priority queues Scribe Notes [src]
This lecture continues our theme of cache-oblivious data structures.

First we'll finally cover the black box we used last lecture to obtain cache-oblivious B-trees: maintain an ordered file with O(1)-size gaps in O(lg2 N) moves per insert/delete in the middle of the file. As an extra bonus, we'll see how to maintain a linked list subject to order queries in O(1) time per insert/delete, which is a black box we used back in Lecture 1 to linearize the version tree when implementing full persistence.

Second we'll cover cache-oblivious priority queues, supporting insert and delete-min in what's usually subconstant time per operation (!), O((1/B) logM/B (N/B)). This will be the first time we see how to adapt to the cache size M, not just the block size B, in a cache-oblivious data structure.

Download Video: 360p, 720p

Lecture notes, page 1/6[previous page][next page][PDF]

Lecture notes, page 1/6[previous page][next page][PDF]

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.