<p>I have been in contact with one of the authors. He confirmed this was a slip.</p>

<p>As stated above, this does not affect, in any way, any of the results of the paper.</p>

CC BY-SA 2.5
2010-10-27T00:52:45.617Z
2010-10-27T00:52:45.617Z
jbapple
<p>In section 2.2 of <a href="http://erikdemaine.org/papers/CacheObliviousBTrees_SICOMP/" rel="nofollow">Cache-Oblivious B-Trees</a>, <em>Strongly Weight-Balanced Search Trees</em> are defined as:</p>

<blockquote>
  <p>For some constant $d$, every node $v$ at height $h$ has $\Theta(d^h)$ descendants.</p>
</blockquote>

<p>They claim:</p>

<blockquote>
  <p>Search trees that satisfy Properties 1 and 2 include weight-balanced B-trees,
  deterministic skip lists, and skip lists in the expected sense.</p>
</blockquote>

<p>Other papers also claim that deterministic skip lists are strongly weight-balanced, including <a href="http://people.csail.mit.edu/jfineman/cobtree.pdf" rel="nofollow">Concurrent Cache-Oblivious B-Trees</a> and <a href="http://people.csail.mit.edu/jfineman/sbtree.pdf" rel="nofollow">Cache-Oblivious Streaming B-trees</a>.</p>

<p>I can't figure out why deterministic skip lists have this property. The <a href="http://scholar.google.com/scholar?cluster=6642479522143429791" rel="nofollow">original paper on deterministic skip-lists</a> notes that</p>

<blockquote>
  <p>As we see from Fig. 1, there exists a one-to-one correspondence between 1-2 skip lists and 2-3 trees.</p>
</blockquote>

<p>It seems to me, however, that 2-3 trees are not strongly weight-balanced, since a node at height $h$ can have anywhere from $2^h$ to $3^h$ descendants.</p>

CC BY-SA 2.5
2010-10-03T01:54:31.573Z
That sounds like a legitimate issue. The mentioned papers all share a coauthor, so it could be a consistent oversight. Have you emailed the authors?
Per Vognsen
CC BY-SA 2.5
2010-10-03T08:23:15.463Z
how critical to the proofs is the tight range for the numnber of descendants ?
Suresh Venkat
CC BY-SA 2.5
2010-10-03T12:49:19.470Z
@Per - I have now emailed the shared coauthor. @Suresh - I am not sure,  but the authors choose to base their structures on weight-balanced B-trees, so my question is not about the validity of the main results.
jbapple
CC BY-SA 2.5
2010-10-03T16:58:53.373Z
Please be careful not to subject an author to a public embarrassment inadvertently.  cf. http://meta.cstheory.stackexchange.com/questions/214/should-there-be-a-protocol-to-notify-authors-if-we-find-an-error-in-a-paper
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-03T19:07:35.390Z
@Tsuyoshi: Since the importance of this possible error is very minor (it does not, as far as I can tell, affect the claimed results of the papers cited in any way), and since most of the "errors" I find in published work are just errors in my own understanding, I thought it would be better to ask here first. Even if this is an error, it is so minor that I suspect it would not lead to any author embarrassment.
jbapple
<ds.data-structures><skip-lists>
Strongly weight-balanced deterministic skip lists
jbapple
# Strongly weight-balanced deterministic skip lists

(Asked by: username_0 on 2010-10-02)

In section 2.2 of [Cache-Oblivious B-Trees](http://erikdemaine.org/papers/CacheObliviousBTrees_SICOMP/), *Strongly Weight-Balanced Search Trees* are defined as:

> For some constant $d$, every node $v$ at height $h$ has $\Theta(d^h)$ descendants.

They claim:

> Search trees that satisfy Properties 1 and 2 include weight-balanced B-trees,
> deterministic skip lists, and skip lists in the expected sense.

Other papers also claim that deterministic skip lists are strongly weight-balanced, including [Concurrent Cache-Oblivious B-Trees](http://people.csail.mit.edu/jfineman/cobtree.pdf) and [Cache-Oblivious Streaming B-trees](http://people.csail.mit.edu/jfineman/sbtree.pdf).

I can't figure out why deterministic skip lists have this property. The [original paper on deterministic skip-lists](http://scholar.google.com/scholar?cluster=6642479522143429791) notes that

> As we see from Fig. 1, there exists a one-to-one correspondence between 1-2 skip lists and 2-3 trees.

It seems to me, however, that 2-3 trees are not strongly weight-balanced, since a node at height $h$ can have anywhere from $2^h$ to $3^h$ descendants.

**Tags:** ds.data-structures, skip-lists
> **Comments:**
> **username_1**: That sounds like a legitimate issue. The mentioned papers all share a coauthor, so it could be a consistent oversight. Have you emailed the authors?  
> **username_2**: how critical to the proofs is the tight range for the numnber of descendants ?  
> **username_0**: @Per - I have now emailed the shared coauthor. @Suresh - I am not sure,  but the authors choose to base their structures on weight-balanced B-trees, so my question is not about the validity of the main results.  
> **username_3**: Please be careful not to subject an author to a public embarrassment inadvertently.  cf. http://meta.cstheory.stackexchange.com/questions/214/should-there-be-a-protocol-to-notify-authors-if-we-find-an-error-in-a-paper  
> **username_0**: @Tsuyoshi: Since the importance of this possible error is very minor (it does not, as far as I can tell, affect the claimed results of the papers cited in any way), and since most of the "errors" I find in published work are just errors in my own understanding, I thought it would be better to ask here first. Even if this is an error, it is so minor that I suspect it would not lead to any author embarrassment.  

---

## 1 answers

### Answer by username_0 on 2010-10-27. Score: 5 | Accepted answer

I have been in contact with one of the authors. He confirmed this was a slip.

As stated above, this does not affect, in any way, any of the results of the paper.


---

