Stark gewichtsausgeglichene deterministische Sprunglisten

11

In Abschnitt 2.2 von Cache-Oblivious B-Trees werden stark gewichtsausgeglichene Suchbäume wie folgt definiert:

Für eine Konstante , jeder Knoten v in der Höhe H hat Θ ( d h ) Nachkommen.dvhΘ(dh)

Sie behaupten:

Suchbäume, die die Eigenschaften 1 und 2 erfüllen, umfassen gewichtsausgeglichene B-Bäume, deterministische Sprunglisten und Sprunglisten im erwarteten Sinne.

Andere Artikel behaupten auch, dass deterministische Sprunglisten stark gewichtsausgeglichen sind, einschließlich gleichzeitiger Cache-Oblivious-B-Bäume und Cache-Oblivious-Streaming-B-Bäume .

Ich kann nicht herausfinden, warum deterministische Sprunglisten diese Eigenschaft haben. Das Originalpapier über deterministische Überspringlisten stellt dies fest

Wie wir aus Fig. 1 sehen, besteht eine Eins-zu-Eins-Entsprechung zwischen 1-2 Überspringlisten und 2-3 Bäumen.

Es scheint mir jedoch, dass 2-3 Bäume nicht stark gewichtsausgeglichen sind, da ein Knoten in Höhe zwischen 2 h und 3 h Nachkommen haben kann.h2h3h

ds.data-structures skip-lists jbapple
quelle
1
Das klingt nach einem legitimen Problem. Die genannten Papiere haben alle einen Mitautor, so dass es sich um ein konsequentes Versehen handeln könnte. Haben Sie den Autoren eine E-Mail geschickt?
Per Vognsen
Wie kritisch für die Beweise ist der enge Bereich für die Anzahl der Nachkommen?
Suresh Venkat
@Per - Ich habe jetzt eine E-Mail an den freigegebenen Mitautor gesendet. @Suresh - Ich bin mir nicht sicher, aber die Autoren entscheiden sich dafür, ihre Strukturen auf gewichtsausgeglichenen B-Bäumen zu basieren, daher geht es bei meiner Frage nicht um die Gültigkeit der Hauptergebnisse.
jbapple
Bitte achten Sie darauf, dass ein Autor nicht versehentlich einer öffentlichen Verlegenheit ausgesetzt wird. vgl. meta.cstheory.stackexchange.com/questions/214/…
Tsuyoshi Ito
@ Tsuyoshi: Da die Wichtigkeit dieses möglichen Fehlers sehr gering ist (soweit ich das beurteilen kann, hat dies keinen Einfluss auf die behaupteten Ergebnisse der zitierten Artikel in irgendeiner Weise) und da die meisten "Fehler", die ich finde, veröffentlicht wurden Arbeit sind nur Fehler in meinem eigenen Verständnis, ich dachte, es wäre besser, zuerst hier zu fragen. Selbst wenn dies ein Fehler ist, ist er so geringfügig, dass ich vermute, dass er nicht zu einer Verlegenheit des Autors führen würde.
jbapple

Antworten:

5

Ich habe mit einem der Autoren Kontakt aufgenommen. Er bestätigte, dass dies ein Ausrutscher war.

Wie oben erwähnt, hat dies keinerlei Auswirkungen auf die Ergebnisse des Papiers.

jbapple
quelle