[+] Memory hierarchy: distribution sweeping via lazy funnelsort; cacheoblivious orthogonal 2D range searching: batched and online  
Our third and final lecture on memory hierarchies is a fun crossover between cacheoblivious data structures and geometric data structures. We'll start with an optimal cacheoblivious sorting algorithm (something we left as a black box in Lecture 8), called Lazy Funnelsort, though we'll skip the analysis, as it's similar to the priority queue. Then we'll see how to combine that algorithm with the sweepline technique from computational geometry to solve batched geometric problems. Specifically, we'll see how to solve batched orthogonal 2D range searching in the sorting bound using this “distribution sweeping” technique. Finally, we'll cover a series of algorithms for regular online orthogonal 2D range searching, including an impressive linearspace cacheoblivious data structure for 2sided (quarterplane) range queries, as well as the trick for shaving off a log log factor of space from a regular 4sided range search data structure. 
Lecture notes, page 1/9 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/9 • [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.