11

In section 2.2 of Cache-Oblivious B-Trees, 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 and Cache-Oblivious Streaming B-trees.

I can't figure out why deterministic skip lists have this property. The original paper on deterministic skip-lists 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.

jbapple
  • 11,184
  • 2
  • 29
  • 50
  • 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? – Per Vognsen Oct 03 '10 at 01:54
  • how critical to the proofs is the tight range for the numnber of descendants ? – Suresh Venkat Oct 03 '10 at 08:23
  • @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 Oct 03 '10 at 12:49
  • 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 Oct 03 '10 at 16:58
  • @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 Oct 03 '10 at 19:07

1 Answers1

5

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.

jbapple
  • 11,184
  • 2
  • 29
  • 50