\documentclass{article} %\input{6854-preamble} \usepackage{scribe} \begin{document} \lecture{1}{11/15/2004}{Erik Demaine}{Dan Ports} Aggarwal \& Vitter 1988 Alternative to RAM model. RAM model doesn't always predict how algorithms will work on real memory. CPU has fast connection to \emph{cache}. Cache size is M. $\frac{M}{B}$ rows of $B$ columns. Main memory is much larger and much slower to access. $B$ columns, but more rows. No cost to access cache memory and perform operations on it. Goal is to minimize number of memory transfers. This isn't exactly the runtime, since runtime includes cache operations too. Transfers take place in blocks of size $B$, so we want to take advantage of locality. Accessing an element requires transferring the entire block.An algorithm that has runtime $T$ can trivially be made to use $\le T$ transfers, but we'd like to use less. $\frac{T}{B}$ is ideal. Scanning Visit each element in order. %$\ceil{\frac{N}{B}} + 1$ memory transfers to visit $N$ elements. This is optimal. Reversing an array. Swap first and last elements. Can be performed using blocks. Two parallel scans: one from the front, one from the back. Can be done in $O(\frac{N}{B})$ time. Requires $M \ge 2B$ cache size. This isn't a problem. Often we'll use $M = \Omega(B^{1+\epsilon})$: tall cache assumption. Search trees. B-trees. nodes containing $b$ values, branching factor $b+1$. $\Theta(\log_b N)$ height. Why is this good for external memory algorithms? Choose $b$ to be (a constant factor less than) $B$, so we can fit a node and all of its child pointers into a block. This gives us $O(\log_{B+1} N)$ access time. Is this optimal? Search problem: given $N$ elements, do some preprocessing, then find the closest element to a given query. Normally $O(\log N)$ binary trees is optimal; here we claim $O(\log_B N)$ is optimal. Claim (information theoretic): searching for $x$ among a sorted list of $N$ elements requires $\Omega(\log_{B+1} N)$ memory transfers. Proof: write down sorted array 1 .. n most succinct encoding of the answer is the index in the array. Goal is therefore to learn $lg N+1$ bits. Initially cache is empty, so we don't have any information. Each memory read reveals at most $B$ elements that we haven't seen before. So we learn where $x$ fits into these elements. Since they were already sorted, we learn $\le \lg B$ bits. So we need $\frac{\lg N+1}{\lg B+1} = \log_{B+1}N$. So B-trees are optimal in terms of memory transfer. They can also be made optimal in time by storing each node as a small balanced binary search tree. Sorting (comparison-based). Bound for sorting is $\Theta(\frac{N}{B} \log_{\frac{M}{B}} \frac{N}{B})$ In the RAM model, we can sort optimally by building a B-tree and extracting the minimum element repeatedly. $O(n \log n)$. But this isn't good in the external memory model: it gets us $O(N \log_{B+1} N)$, which isn't quite good enough. Merge sort. Can divide a problem of size $N$ into two sorting subproblems of size $\frac{N}{2}$, plus a merge. The merging can be done in $O(\frac{N}{B})$ time using parallel scanning. \[ T(N) = 2T(\frac{N}{2}) + O(\frac{N}{B} \] Recursion tree starts at N/B, goes to 1/2 N/B x 2 + 1/4 N/B x 4 ... up to depth M. N/B work on each level, log N/M levels. \[T(N) = \frac{N}{B} \log \frac{N}{M}\] Almost good, but we want a log base of M/B. How do we get this? M/B-way mergesort (as opposed to binary mergesort). Split a subproblem of size $N$ into $M/B$ subproblems of size $\frac{N}{M/B}$. This is the correct size because it allows us to fit the array in memory. (FIXME: explain better) Recursion is \[ T(N) = \frac{M}{B} T\left(\frac{N}{\frac{M}{B}}\right) + O\left(\frac{N}{B}\right) \] FIXME: recursion solution by recursion tree \[ T(N) = \frac{N}{B}\left(1 + \log_{\frac{M}{B}} \frac{N}{M}\right) \] \[ T(N) = \frac{N}{B}\left(2 + \log_{\frac{M}{B}} \frac{N}{B}\right) \] Is this optimal? (in comparison model) Need to learn $\lg N!$ bits. Actually just $\lg \frac{N!}{B!}$ since we can sort a block instantly. FIXME: make sure this carries through in the analysis. Can always keep cache sorted. (It's free, might as well) By reading $B$ elements, we learn where it fits in among the cached elements: block read learns which of the $\binom{M+B}{B}$ possible interleavings of the $B$ elements we have. Gives us $\lg \binom{M+B}{B}$ bits. Need $\lg N!$ bits, so we need \[ \frac{\lg N!}{\lg \binom{M+B}{B}}\] accesses. $\lg N!$ is $N \lg N$ to a constant factor. \[\lg \frac{(M+B)!}{M!B!} \approx (M+B) \lg (M+B) - M \lg M - B \lg B\] \[ \approx M \lg M + B \lg M - M \lg M - B \lg B \] \[ = B \lg \frac{M}{B} \] \[\frac{ N \lg \frac{N}{B}}{B \lg \frac{M}{B}} = \frac{N}{B} \lg_\frac{M}{B}} \frac{N}{B} \] Buffer tree: Arge 1995 Would like a data structure that's better for sorting. $O\left(\frac{1}{B} \log_{\frac{M}{B}} \frac{N}{B}\right)$ amortized memory transfers per insert, delete, batched search, and delete-min operations. This is a rather impressive bound since it's usually less than 1 (which is why it's an amortized bound). What's a batched search? Make a request for a search, don't get an immediate answer. This is also a priority queue, but more general. Looks like a B-tree. Branching factor is $M/B$. Leaves will have $\Theta(B)$ elements and no buffer. For each internal node, also have a buffer of size $M$. Requests are stored in the buffer before being pushed lazily into children (standard data structures technique). \begin{verbatim} Insert(x): - Append x to the root buffer, with ``append'' insert classification and timestamp. - If root buffer is full, - sort the buffer. $O(M/B \lg_{M/B} M/B) = O(M/B)$. - distribute items in buffer to buffers of appropriate children %(possibly triggering overflows there) Dealing with $M$ elements, and $M/B$ children = $M/B$ buffers we might be touching. Need to pay O(M/B) to fetch buffers from memory and start writing. But we have M elements to charge it to. $O(M/B)$ as well. - check for children overflows Overflow: - sort $\le M$ old elements in buffer - merge with newly added elements (which are in sorted order) just inserted from parent - $O(\frac{M}{B})$ time. - distribute to children - check for overflowing children Overflow-leaf: - just split leaf like a M/B-tree. Happens rarely. \end{verbatim} Analysis: O(M/B) transfers per overflow involving at least M elements. How many times do we overflow per inserting $N$ elements? Each element is involved in log_{M/B} N/B overflows, since this is the height of the tree and it can only move down. Charge transfers per overflow to $M$ elements involved: 1/B per. Each element gets charged once per overflow it's involved in, so amortized cost per element is 1/b log_{M/B} N/B. This is the sorting bound divided by n Flush: clear all buffers Can't use typical amortized analysis because buffers might not be full, but it can't take more time than it would if they did. time is O(N/B log_{M/B} N/B). Delete: insert timestamped delete element into the root buffer and propagate it down as before. When an insert and delete for the same element (with timestamps ok) meet in some buffer, they cancel each other out. In a leaf, do a B-tree delete rather than a B-tree delete. Offline searches (batched searches): Insert searches into the buffer. If a search hits an identical insertion, that's the exact answer. Otherwise, when the search hits a leaf, do a b-tree search and return the closest. Range-search(x,y): find all elements between x and y O(1/B log_{M/B} N/B + \frac{\abs{output}}{B}) Insert x and y endpoints, and accumulate answers ``off to the side'' Delete-min: Extra buffer of $M$ min elements - always in cache (being sloppy with constant factors here). Delete-min: delete-min of buffer of min. OK until buffer empties. Then we need the next $M$ smallest elements. This is a search tree, so the minimum elements will be along the left spine. Walk down the left spine, flushing. Refills buffer. Also need to check for new mins on insert, but doesn't change runtime since all in cache. \end{document}