11
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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? $\endgroup$
    – Per Vognsen
    Oct 3, 2010 at 1:54
  • $\begingroup$ how critical to the proofs is the tight range for the numnber of descendants ? $\endgroup$
    – Suresh Venkat
    Oct 3, 2010 at 8:23
  • $\begingroup$ @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. $\endgroup$
    – jbapple
    Oct 3, 2010 at 12:49
  • $\begingroup$ Please be careful not to subject an author to a public embarrassment inadvertently. cf. meta.cstheory.stackexchange.com/questions/214/… $\endgroup$
    – Tsuyoshi Ito
    Oct 3, 2010 at 16:58
  • $\begingroup$ @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. $\endgroup$
    – jbapple
    Oct 3, 2010 at 19:07

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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