Zdecydowanie zrównoważone deterministyczne listy pominięć

W sekcji 2.2 Cache-niepomny B-drzew , stanowczo Weight Balanced wyszukiwania Drzewa są zdefiniowane jako:

Dla niektórych stałych , każdy węzeł na wysokości ma potomków . $d$ $v$ $h$ $\Theta(d^h)$

Oni twierdzą:

Drzewa wyszukiwania spełniające właściwości 1 i 2 obejmują zrównoważone pod względem masy drzewa B, deterministyczne listy pominięć i listy pominięć w oczekiwanym znaczeniu.

Inne artykuły również twierdzą, że deterministyczne listy pominięć są silnie zrównoważone pod względem wagi, w tym współbieżne B-Drzewa B-drzewa nieobsługiwane przez pamięć podręczną i B-drzewa nieobsługujące pamięci podręcznej .

Nie mogę zrozumieć, dlaczego deterministyczne listy pominięć mają tę właściwość. Oryginalny papier na deterministycznych skip-list zauważa, że

Jak widać na ryc. 1, istnieje korespondencja jeden do jednego między 1-2 listami pomijanymi a 2-3 drzewami.

Wydaje mi się jednak, że 2-3 drzewa nie są silnie zrównoważone pod względem masy, ponieważ węzeł na wysokości może mieć od do potomków. $h$ $2^h$ $3^h$

ds.data-structures skip-lists jbapple
źródło

To brzmi jak uzasadniony problem. Wszystkie wspomniane artykuły są współautorami, więc może to być stały nadzór. Czy wysłałeś e-mail do autorów?

Per Vognsen

jak krytyczny dla dowodów jest wąski zasięg dla liczby potomków?

Suresh Venkat

@Per - Wysłałem e-mailem do współautora. @Suresh - Nie jestem pewien, ale autorzy zdecydowali się oprzeć swoje struktury na zrównoważonych pod względem masy drzewach B, więc moje pytanie nie dotyczy ważności głównych wyników.

jbapple

Zachowaj ostrożność, aby przypadkowo nie narazić autora na publiczne zawstydzenie. por. meta.cstheory.stackexchange.com/questions/214/…

Tsuyoshi Ito

@Tsuyoshi: Ponieważ znaczenie tego możliwego błędu jest bardzo niewielkie (o ile mi wiadomo, nie wpływa ono na deklarowane wyniki cytowanych artykułów w żaden sposób), a ponieważ większość „błędów” znajduję w opublikowanych praca jest tylko błędem w moim rozumieniu, pomyślałem, że lepiej byłoby najpierw zapytać tutaj. Nawet jeśli jest to błąd, jest tak niewielki, że podejrzewam, że nie doprowadziłby do zawstydzenia autora.

jbapple,

Zdecydowanie zrównoważone deterministyczne listy pominięć

Odpowiedzi: