Przechowywanie bardzo dużych wykresów na algorytmach partycjonowania wykresów na dysku/strumieniu?

Question

Załóżmy, że mam bardzo duży, nieukierunkowany, nieważony wykres (rozpoczynający się od setek milionów wierzchołków, ~ 10 krawędzi na wierzchołek), nierozdzielony i przetwarzany tylko przez jeden wątek i że chcę wykonać w nim wiele wyszukiwań . Oczekuję, że będą one powiązane z I/O, więc potrzebuję układu strony dysku dobrej dla BFS, miejsce na dysku nie jest problemem. Wyszukiwanie może rozpocząć się na każdym wierzchołku z równym prawdopodobieństwem. Intuicyjnie oznacza to zmniejszenie liczby krawędzi między wierzchołkami na różnych stronach dysku, co jest problemem z partycjonowaniem wykresu.

Sam wykres wygląda jak spaghetti, pomyśl o losowym zestawie losowo połączonych punktów, z pewną tendencją do krótszych krawędzi.

Problem polega na tym, że jeden podział wykresu jest tak duży? Dostępne graficzne partycje, które znalazłem, działają z wykresami pasującymi tylko do pamięci. Nie mogłem znaleźć żadnych opisów ani implementacji algorytmów partycjonowania wykresów strumieniowych.

OR, może jest alternatywa dla wykresu partycjonowania, aby uzyskać układ dysku, który działa dobrze z BFS?

W tej chwili używam faktu, że wierzchołki mają współrzędne przestrzenne z nimi związane i umieszczają wierzchołki na dysku w porządku sortowania Hilberta. W ten sposób przestrzenne wierzchołki lądują na tej samej stronie, ale obecność lub brak krawędzi między nimi jest całkowicie ignorowany. Czy mogę zrobić lepiej?

Alternatywnie, mogę podzielić wykres na części za pomocą porządku sortowania Hilberta dla wierzchołków, podzielić podgramy, zszyć je i zaakceptować słabe partycje na szwach.

Niektóre rzeczy mam spojrzał na już:

1. How to store a large directed unweighted graph with billions of nodes and vertices
2. http://neo4j.org/ - Znalazłem informacje o zerowej jak to zrobić wykres układ na dysku

implementacje działowe (chyba, że ​​jestem mylone, wszystkie z nich muszą pasować do wykresu):

1. http://glaros.dtc.umn.edu/gkhome/views/metis
2. http://www.sandia.gov/~bahendr/chaco.html
3. http://staffweb.cms.gre.ac.uk/~c.walshaw/jostle/
4. http://www.cerfacs.fr/algor/Softs/MESHPART/

EDIT: Informacje o tym, jak to wygląda i wykresy, które można uruchomić BFS wszędzie. EDYCJA: pomysł na podział subgraphs

Answer 1

Żaden algorytm naprawdę nie musi "pasować do pamięci" - zawsze można w razie potrzeby wyświetlać i odkładać rzeczy. Ale nie chcesz, aby obliczenia trwały zbyt długo - a globalny podział wykresów w przypadku ogólnym to problem NP-zupełny, który jest "nieuzasadniony długo" dla większości problemów, które nie mieszczą się w pamięci.

Na szczęście, chcesz wykonać wiele wyszukiwań, co oznacza, że ​​potrzebujesz formatu, w którym pierwszeństwo jest łatwym obliczeniem. Nie znam żadnych algorytmów, które by to zrobiły, ale możesz zbudować swój własny, pierwszy układ, jeśli chcesz pozwolić sobie na odrobinę dodatkowej przestrzeni dyskowej.

Jeśli krawędzie nie są obciążone w kierunku lokalnych interakcji, rozplątanie wykresu będzie trudne. Jeśli są one stronnicze względem lokalnych interakcji, sugeruję algorytm podobny do następującego:

• Wybierz losowy zestaw wierzchołków jako punkt początkowy z całego zestawu danych.
• Dla każdego wierzchołka zbieraj wszystkie sąsiednie wierzchołki (przechwytuje jeden zestaw danych).
• Dla każdego zestawu sąsiednich wierzchołków zbierać zestaw sąsiadów sąsiednich i ranguj je zgodnie z liczbą krawędzi do nich podłączonych. Jeśli nie masz miejsca na stronie, aby je wszystkie przechowywać, zachowaj najbardziej połączone wierzchołki. Jeśli masz miejsce na zapisanie ich wszystkich, możesz wyrzucić najmniej przydatne (np. Jeśli ułamek krawędzi utrzymywanych w obrębie strony/ułamek wierzchołków wymagających współczynnika przechowywania spadnie "za nisko" - gdzie "za mało" będzie zależeć od tego, jak bardzo zakres poszukiwań jest naprawdę potrzebny i czy można wykonać jakiekolwiek przycinanie i tak dalej - wtedy nie włączaj tych w sąsiedztwo
• Powtórz proces zbierania i klasyfikowania sąsiadów aż do wypełnienia twojej okolicy (np. wypełnia jakiś rozmiar strony, który Ci odpowiada) Następnie sprawdź powtarzalność losowo wybranych startów Jeśli masz małą liczbę wierzchołków pojawiających się w obu, usuń je z jednej lub drugiej strony, w zależności od tego, która z nich złamie mniej krawędzi. liczba wierzchołków pojawiających się w obu, zachowaj sąsiedztwo z najlepszym (wierzchołki w sąsiedztwie/zepsutą krawędzią) i wyrzuć drugą.

Teraz masz kilka lokalnych okolic, które są w przybliżeniu lokalnie optymalne w tym zakresie - pierwsze wyszukiwania zwykle wpadają do środka. Jeśli twoje pierwsze wyszukiwanie bardzo skutecznie przycina nieproduktywne gałęzie, to prawdopodobnie jest wystarczająco dobre. Jeśli nie, prawdopodobnie chcesz, aby sąsiednie dzielnice były skupione.

Jeśli nie potrzebujesz sąsiednich okolic, aby skupić się zbytnio, odłóż na bok wierzchołki, które zgrupowałeś w dzielnice, i powtórz proces na pozostałych danych, dopóki wszystkie wierzchołki nie zostaną uwzględnione. Zmieniasz każdy identyfikator wierzchołka na (vertex, neighbour) i gotowe: gdy podążasz za krawędziami, wiesz dokładnie, którą stronę złapać, a większość z nich będzie bliska, biorąc pod uwagę konstrukcję.

Jeśli potrzebujesz przylegających dzielnic, musisz śledzić rosnące dzielnice. Powtarzasz poprzedni proces (wybieraj losowo, powiększaj dzielnice), ale teraz ustawiaj sąsiadów według liczby krawędzi, które spełniają w sąsiedztwie, jaką część krawędzi, które opuszczają sąsiedztwo, znajduje się w istniejącej grupie. Możesz potrzebować współczynników ważenia, ale prawdopodobnie coś takiego zrobi.

Teraz to nie globalnie lub nawet lokalnie optymalny, ale to albo coś bardzo podobnego powinno dać ładnie lokalnie podłączony struktury i powinny pozwalają stworzyć zestaw zakrycie dzielnicach, które mają stosunkowo wysoką wzajemnych połączeń.

To zależy od tego, czy Twoje pierwsze połacie suszą się, czy nie. Jeśli tak, to niedrogą rzeczą do zrobienia jest maksymalizacja lokalnych połączeń między sieciami. Jeśli tak nie jest, to należy zminimalizować zewnętrzną łączność - i w takim przypadku proponuję po prostu zbieranie szerokości - najpierw ustawia się do pewnego rozmiaru i zapisuje je (z duplikacją na krawędziach zestawów - ty nie jest źle ograniczona przez miejsce na dysku twardym, prawda?).

Answer 2

Może chcesz spojrzeć na HDF5. Pomimo, że H oznacza Hierarchiczny, może przechowywać wykresy, sprawdzać dokumentację pod słowem kluczowym "Grupy" i jest przeznaczony dla bardzo dużych zestawów danych. Jeśli dobrze rozumiem, pliki "HDF5" mogą być rozproszone w wielu "plikach" o/s. Teraz HDF5 to tylko struktura danych, a także zestaw bibliotek do manipulacji strukturą danych na niskim i wysokim poziomie. Poza tym nie mam pojęcia o przesyłaniu strumieniowych algorytmów partycjonowania wykresów, ale trzymam się stwierdzenia, że ​​jeśli zdobędziesz strukturę danych, odpowiednie algorytmy staną się łatwiejsze do wdrożenia.

Co już wiesz o mega-wykresie? Czy naturalnie dzieli się na gęste podgrafy, które same są słabo połączone?Czy topologiczny rodzaj wykresu byłby lepszą podstawą do przechowywania na dysku niż istniejący rodzaj przestrzenny?

W przypadku braku wyraźnych odpowiedzi na takie pytania, może po prostu musisz ugryźć punktor i kilkakrotnie przeczytać wykres, aby zbudować partycje, w takim przypadku potrzebujesz najszybszych operacji we/wy, którymi możesz zarządzać, i zaawansowanego układu partycji. na węzłach jest ładne, ale nie tak ważne. Jeśli możesz podzielić wykres na pod-wykresy, które same mają pojedyncze krawędzie do innych pod-wykresów, być może uda ci się uczynić problem łatwiejszym.

Chcesz dobrego układu BFS, ale BFS jest zwykle stosowany do drzew. Czy twój wykres ma unikalny katalog główny, od którego można zacząć wszystkie BFS? Jeśli nie, to układ BFS z jednego wierzchołka będzie suboptymalny dla BFS z innego wierzchołka.

Answer 3

Sprawdź ten wpis na blogu:

"szukaj wykres wszerz za pomocą algorytmu iteracyjnego mapa-zmniejszenie"

http://www.johnandcailin.com/blog/cailin/breadth-first-graph-search-using-iterative-map-reduce-algorithm