Lecture notes, page 1/9 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/9 • [previous page] • [next page] • [PDF]
| [+] Memory hierarchy: distribution sweeping via lazy funnelsort; cache-oblivious orthogonal 2D range searching: batched and online | ||||
| Our third and final lecture on memory hierarchies is a fun crossover between cache-oblivious data structures and geometric data structures. We'll start with an optimal cache-oblivious 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 linear-space cache-oblivious data structure for 2-sided (quarterplane) range queries, as well as the trick for shaving off a log log factor of space from a regular 4-sided 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.