<p>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".</p>

<p><strong>edit:</strong></p>

<p>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&#39;}$ (the static binary tree) as having volume 1.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-01-28T10:44:03.360Z
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$ ...
Juho
CC BY-SA 3.0
2012-01-28T16:36:43.853Z
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.
jbapple
CC BY-SA 3.0
2012-01-28T16:48:01.310Z
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.
Jeffε
CC BY-SA 3.0
2012-01-28T17:07:09.973Z
@JɛﬀE: 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.
jbapple
CC BY-SA 3.0
2012-01-28T18:13:23.183Z
@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.
Juho
CC BY-SA 3.0
2012-01-28T03:52:58.460Z
2012-01-28T16:34:32.253Z
2012-01-28T16:34:32.253Z
jbapple
<p>Lately I have been studying cache-oblivious data structures and algorithms. I was reading about the cache-oblivious B-tree from the <a href="http://www.cs.au.dk/~gerth/papers/cacheoblivious05.pdf" rel="nofollow noreferrer">Handbook of Data Structures and Applications</a>, with hopes of actually implementing it and doing some benchmarking.</p>

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

<blockquote>
  <p>To insert a new element into the structure we ﬁrst 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 ﬁnd the lowest ancestor v of w satisfying $γ_i$ ≤ ρ(v) ≤ $τ_i$, where $i$ is the level of $v$.</p>
</blockquote>

<p><img src="https://i.sstatic.net/R5t2h.png" alt="A complete static tree of height H"></p>

<p>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.</p>

<p>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 <em>lowest ancestor</em> or the lowest ancestor $v$ should satisfy <strong>not</strong> $γ_i$ ≤ ρ(v) ≤ $τ_i$ but $γ_i$ &lt; ρ(v) &lt; $τ_i$.</p>

<p>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$.</p>

<ds.algorithms><ds.data-structures>
Updates on a cache-oblivious B-tree
Juho
# Updates on a cache-oblivious B-tree

(Asked by: username_0 on 2012-01-27)

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](http://www.cs.au.dk/~gerth/papers/cacheoblivious05.pdf), 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 ﬁrst 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 ﬁnd the lowest ancestor v of w satisfying $γ\_i$ ≤ ρ(v) ≤ $τ\_i$, where $i$ is the level of $v$.

![A complete static tree of height H](https://i.sstatic.net/R5t2h.png)

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$.

**Tags:** ds.algorithms, ds.data-structures


---

## 1 answers

### Answer by username_1 on 2012-01-28. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: 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$ ...  
> **username_1**: 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.  
> **username_2**: 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.  
> **username_1**: @JɛﬀE: 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.  
> **username_0**: @username_1 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.  

---

