Czy przydatne są probabilistyczne struktury danych wyszukiwania?

9

SkipList zapewnia to samo $O(\log n)$ ogranicza wyszukiwanie jako drzewo zrównoważone z tą zaletą, że ponowne zbalansowanie nie jest konieczne. Ponieważ SkipList jest konstruowany przy użyciu losowych rzutów monetą, granice te obowiązują tylko tak długo, jak długo struktura SkipList jest wystarczająco „zrównoważona”. W szczególności z prawdopodobieństwem $1/n^c$ dla jakiejś stałej $c>0$ , zrównoważona struktura może zostać utracona po wstawieniu elementu.

Powiedzmy, że chcę użyć listy pominięć jako zaplecza pamięci w aplikacji internetowej, która potencjalnie działa wiecznie. Zatem po pewnej wielomianowej liczbie operacji bardzo prawdopodobne jest, że zrównoważona struktura SkipList zostanie utracona.

Czy moje rozumowanie jest prawidłowe? Czy takie probabilistyczne struktury wyszukiwania / przechowywania danych mają praktyczne zastosowania, a jeśli tak, to w jaki sposób można uniknąć powyższego problemu?

Edycja: Zdaję sobie sprawę, że istnieją deterministyczne warianty SkipList, które są znacznie bardziej skomplikowane do wdrożenia w porównaniu do (klasycznej) losowej SkipList.

data-structures search-trees probabilistic-algorithms

— ktoś
źródło

1

Jakie konkretne aplikacje masz na myśli?

— Pratik Deoghare

6

Nie sądzę, aby istnieje wielomianowe prawdopodobieństwo utraty „równowagi”. Po wstawieniu elementu do listy pominięć budujesz nad nim wieżę kopii, podrzucając monetę, aż dojdzie do głowy.

Kiedy osiągniesz szczyt, masz warstwy z coraz mniejszą liczbą elementów. Ponieważ wieża ma wysokość $k$ z prawdopodobieństwem $2^{-k}$ , na wysokości jest element $k$ z prawdopodobieństwem (związkowym) mniejszym niż $n/2^k$ . Stąd posiadanie elementu na poziomie $c\log n$ ma prawdopodobieństwo mniej niż $1/n^c$ . Wieże wysokości $\omega(\log n)$ mają prawdopodobieństwo subpolinomalne. Pozwolić $M$ być maksymalnym poziomem, to mamy

E [M] = \sum_{k \geq 1} P r (M \geq k) \leq \log (n) + \sum_{k \leq \log (n)} n / 2^{k} = \log (n) + 2.

$E[M] = \sum_{k\geq 1} Pr(M\geq k) \leq \log(n) + \sum_{k\le \log(n)} n/2^k = \log(n) + 2.$

Ponadto na poziomie $k$ tam są $n/2^k$ elementy o bardzo wysokim prawdopodobieństwie, ponieważ jest to suma $n$ niezależne zmienne losowe i można użyć granicy Chernova.

Ponieważ możesz pokazać, że wykonujesz tylko stałą liczbę kroków na poziom (z bardzo dużym prawdopodobieństwem!), Koszty wyszukiwania są logarytmiczne.

Tak więc musiałbyś być bardzo pechowy, aby skończyć z niezrównoważoną listą. Pamiętaj, że „szczęście” jest tutaj niezależne od twoich danych, w przeciwieństwie do na przykład w niezrównoważonych drzewach wyszukiwania. Przerzucanie monet na listach pomijania jest zawsze losowe.

O ile mi wiadomo, listy pominięć mają duże znaczenie praktyczne, ponieważ można je stosunkowo łatwo wdrożyć jako struktury wyszukiwania bez blokad, z oczywistymi korzyściami. Z drugiej strony B-drzewa są raczej trudne do osiągnięcia w przypadku jednoczesnego dostępu.

— adrianN
źródło

Oczekiwana głębokość drzew wyszukiwania binarnego jest również logarytmiczna; dlaczego tutaj sytuacja jest lepsza? (Zakładasz także losowe permutacje, prawda?)

— Raphael

2

W drzewach wyszukiwania głębokość zależy od danych. Jeśli podajesz liczby losowe, ma ono głębokość logarytmiczną z bardzo dużym prawdopodobieństwem. Jednak w praktyce dane nie są losowe. Listy pomijania nie używają danych jako źródła losowości, więc ten problem nie istnieje.

— adrianN

1

Listy pomijania mają inne właściwości, które mogą uczynić je atrakcyjnymi w sytuacjach, w których używane są operacje inne niż wstawianie / wyszukiwanie / usuwanie.

Na przykład listy pominięć mają $O(1)$ oczekiwane lokalne aktualizacje, gdy znana jest lokalizacja modyfikacji. Z pewnością jest to możliwe w $O(1)$ najgorszy przypadek w przypadku niektórych zrównoważonych drzewek wyszukiwania binarnego, ale implementacja tych struktur jest dość skomplikowana.

Ponadto listy pomijania są popularnym sposobem wdrażania współbieżnych struktur wyszukiwania opartych na porównaniu. Historycznie zrównoważone drzewa poszukiwań nie działały tak dobrze przy dużej równoczesnej rywalizacji.

— jbapple
źródło