6
$\begingroup$

Lately I have been studying cache-oblivious data structures and algorithms. I was reading about the cache-oblivious B-tree from the Handbook of Data Structures and Applications, with hopes of actually implementing it and doing some benchmarking.

Section 38.3.1 of the book talks about the density based approach. The vEB-layout and the density thresholds seem fine, but I am missing something (perhaps even trivial) from the updates. The text explains:

To insert a new element into the structure we first locate the position in $T$ of the new node $w$. If the insertion of $w$ violates the height bound $H$, we rebalance $T$ as follows: First we find the lowest ancestor v of w satisfying $γ_i$ ≤ ρ(v) ≤ $τ_i$, where $i$ is the level of $v$.

A complete static tree of height H

Looking at the figure, let's consider a scenario: suppose we want to insert an item with value 15. We check to see that it cannot be inserted since the height bound $H$ would be violated. Hence we must find the lowest ancestor $v$ of $w$ satisfying the mentioned bounds. If we now work towards the top of tree trying to find a suitable ancestor, we find it immediately (the item with value 13). It clearly satisfies the bounds, since its ρ is 1.

It would make a lot more sense to me if the ancestor at which we should stop is the one with value 8. Right now I see two cases: either I don't know the exact definition of lowest ancestor or the lowest ancestor $v$ should satisfy not $γ_i$ ≤ ρ(v) ≤ $τ_i$ but $γ_i$ < ρ(v) < $τ_i$.

I also took a look at Cache-oblivious B-trees by Bender, Demaine and Farach-Colton. This paper also defines the bound as $γ_i$ ≤ ρ(v) ≤ $τ_i$.

Improve this question
$\endgroup$
2
$\begingroup$

Perhaps one must consider the parent of the node to be inserted as having weight 2. Then the "find the lowest in-density ancestor" is equivalent to "find the least amount of rebuilding needed to maintain the invariants".

edit:

In the physical world, density is defined as mass divided by volume. This corresponds to the density notion in these cache-oblivious B-trees if we view each "item" as having mass 1 and each location in $\mathcal{T'}$ (the static binary tree) as having volume 1.

Before inserting an item, we want to make sure that once it is in the tree it is in a subtree that is within its prescribed density bounds. We therefore imagine that it is already there in the tree, but taking up no space yet. The reason why we might imagine that it presently takes up no space is that, well, there might not be any space for it to take up right now, as in your example.

To make sure that the tree the new item will be in is within bounds, we need to find its closest ancestor that we actually can rebalance (without increasing the height) and insert the item into while still remaining within the density boundaries. To do so, we find the nearest ancestor that will be within the density boundaries, which means using its current "volume" and its soon-to-be-correct "mass". To get the latter, we must include an extra unit of mass for the item we are about to insert.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Sorry, I don't think I follow, can you elaborate? Do you mean density when you say weight, or something else? I wonder if everything would work if I just find the closest ancestor in a bottom-up fashion satisfying $γ_i$ < ρ(v) < $τ_i$ ... $\endgroup$ – Juho Jan 28 '12 at 10:44
  • $\begingroup$ No, I mean the numerator of density when I say weight. It is possible that everything would work out with your strict bounds, but I'm trying to understand the paper as if it is correct but not as explicit as it could be, rather than concluding that there is an error. I have edited my answer to try to be more explicit. $\endgroup$ – jbapple Jan 28 '12 at 16:36
  • $\begingroup$ The newly inserted node increases the density of all of its ancestors. In particular, after inserting 15, but before rebalancing the tree, node (13) has density 2/3, not 1, because it has a right child but no left child. $\endgroup$ – Jeffε Jan 28 '12 at 16:48
  • $\begingroup$ @JɛffE: In that case, isn't node (13) within boundaries after the insertion but before rebalancing? I would find that strange, since node (13) should not be the only one rebuilt, but it would be the nearest ancestor within balance. $\endgroup$ – jbapple Jan 28 '12 at 17:07
  • $\begingroup$ @jbapple Thanks. Indeed, what you suggest seems to make sense. I will work through more example cases on paper and inspect the paper more closely before accepting. $\endgroup$ – Juho Jan 28 '12 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.