Równoległe wyszukiwanie dynamiczne

Czy istnieje naturalny równoległy analog do czerwono-czarnych drzew o podobnych lub nawet niezbyt gorszych właściwościach do aktualizacji, przy jednoczesnym zapewnieniu odpowiedniej wydajności pracy?

Mówiąc bardziej ogólnie, co możemy zrobić dla wyszukiwania równoległego z aktualizacjami?

— Suresh Venkat
źródło

Jakie w szczególności właściwości chcesz zachować lub zmienić na „nie strasznie gorzej”? Jak ważne jest to, że stan równowagi jest nadal taki sam jak w przypadku drzew czerwono-czarnych? Czy dopuszczalne granice, jak w równoległych listach pominięć, byłyby do przyjęcia?

— jbapple

Myślę, że oczekiwane granice byłyby w porządku. Jest to sytuacja, w której bardzo często uderzamy w strukturę danych o zaktualizowane wartości kluczy, więc mówiąc precyzyjnie, nawet wydajne operacje na klawiszach zmiany są bardzo dobre. Czy masz dobre referencje dla współbieżnych list pomijania?

— Suresh Venkat

Książka Herlihy & Shavit, Sztuka programowania wieloprocesorowego lub „Listy bez linków i listy pomijania” lub java.util.concurrent lub Practical -free-free . Czy zastanawiałeś się nad użyciem współbieżnej tabeli mieszającej, takiej jak tablica mieszająca klasy ?

— jbapple,

Właściwie nie. Niestety jestem analfabetą w zakresie stosowanych metod. Dzięki za referencje.

— Suresh Venkat

Odpowiedzi:

Z tego, co mogę powiedzieć, strategie obejmują rozluźnienie warunków równowagi, a następnie przeprowadzanie aktualizacji równoważenia w seriach. Oto artykuł Hanke i in., 1997 [PDF] , który moim zdaniem koncentruje się na ich technice agregowania i rozwiązywania operacji aktualizacji, aby można je było wykonywać jednocześnie.

— James King
źródło

Myślę, że możesz znaleźć ciekawą odpowiedź w książce Okasaki Purely Functional Data Structures . W tej książce pokazano wiele struktur danych, dzięki czemu każda aktualizacja nie jest droga (zwykle zajmuje tylko czas stały lub logarytmiczny).

Powiedzmy, że „d” jest strukturą tuż przed czasem, w którym musisz się ponownie wyważyć. W czysto funkcjonalnej strukturze danych masz trwałe struktury danych, dlatego możesz dodawać rzeczy do „d” i trzeba ponownie balansować razy. Dlatego zamortyzowana złożoność nie działa w tym ustawieniu, a on stworzył inny sposób uzyskania dobrego algorytmu, w którym każdy krok z aktualizacjami nie jest drogi. $n$ $n$

— Arthur MILCHIOR
źródło

Myślę, że bez dalszych modyfikacji drzewa wyszukiwania o czysto funkcjonalnym serializowaniu wszystkich aktualizacji, a zatem słabo działające w przypadku niezgodności zapisu.

— jbapple