even though the algorithm does not .
- We look at a particuar level of recursion. We will call it a "level of detail" straddling B.
- We will have large triangles of size $\geq B$, inside which there are smaller triangles of size $\leq B$ (reminds me of sierpinski).
- We know that the algorithm recursively lays it out, and triangle stores everything "inside" it in a contiguous region . So we stop at the requisite size where we know that the tree's triangles themselves contain triangles which fit into the block size.
- A little triangle of size less than B can live in at most two memory blocks by straddling a block boundary: by eg. having $(B-1)$ bits in one block and a single bit in another block.
1 2 3 4 5 6 7 8 <- index
| | | <- boundary
|-xxxxxxx-----| <- data
- The question is that on a root-to-leaf bpath, how many such triangles do we need to visit. Since we repeatedly divide the nodes in half with respect to height until the little triangle has number of nodes less than $B$, the height is going to be $O(\log B)$ since it's still a binary tree.
- total height in $O(\log N)$.
- so height of "chunked tree" where we view each triangle as a single node is $\log N / \log B = \log_B n$.
- insight : ou data structure construction in some sense permits us to "binary search on $B$" since we divide the data structure into levels based on $B$. if $B = N$, then the full data structure fits into memory and we're good.
§ Black box: ordered file maintainince
We need a black box: ordered file maintainance (linked list for arrays)
- Store $n$ elements in specified order in an array of linear size $O(N)$. Array permits gaps.
- updates: delete element, insert elements between 2 elements.
- cannot do this in linear time, but we can move elements in an interval of size $\log^2(N)$ amortized.
- We need $O(1)$ scans for the data structure.
§ Next: dynamic BST (inserts and deletes): layout
we take a VEB static tree on top of an ordered file. Tree is a segtree
that has max of nodes. Leaves are the members of the ordered file.
§ Updates
- search for node.
- update ordered file.
- propogate updates into the tree. This will have to be done in post-order because we need the leaves to be fixed before we can update the parent
max
.
§ Updates: analysis.
- look at level of detail that straddles $B$.
- Let us look at the bottom 2 levels.
- Note that when we perform post-order inside a triangle that has 3 triangles of size $\leq B$, we need to alternate between parent triangle and child triangle. Since the parent triangle is of size $\leq B$ and can therefore take at most $2B$ blocks of memory, similarly the child can take at most $2B$blocks of memory.
- So if our cache can hold $4$ blocks of memory, we're done. We won't need to kick anything out when performing the post-order traversal.
- For levels that are above the bottom 2 levels, we're still OK. there are not many triangles! / not many nodes! (
1:16:00
in the video)
§ References