Skuteczny sposób na wdrożenie funkcji LinkedIn, takiej jak" Jak jesteś połączony"?
LinkedIn ma tę fajną funkcję, w której podczas odwiedzania profilu jakiegoś użytkownika LinkedIn podpowiada, w jaki sposób łączysz się z tym użytkownikiem za pośrednictwem sieci.
Zakładając, że użytkownik i właściciel profilu są dwoma węzłami wykresu, gdzie węzły reprezentują użytkowników, a krawędź reprezentuje przyjaźń, prostym rozwiązaniem może być bfs zaczynając od obu węzłów do pewnego poziomu i sprawdzić, czy są jakieś przecięcia. Skrzyżowaniami byłaby sieć łącza-węzły.
Chociaż brzmi to schludnie, problem polega na tym, że aby określić przyjaciół każdej osoby, potrzebne jest osobne zapytanie DB. Gdy sieć idzie głębiej niż 2 poziomy, byłoby to bardzo czasochłonne algorytm. Czy istnieje skuteczniejsza alternatywa? Jeśli nie, jak możemy dodać lepszą obsługę sprzętową (obliczenia równoległe, siatki, rozproszone bazy danych itp.), aby skrócić czas potrzebny na obliczenia?
2 answers
Możesz zobaczyć jak to zrobić w artykule wykresy w bazie danych: SQL meets social networks autorstwa Lorenzo Alberton. Przykładowy kod jest napisany dla PostgreSQL przy użyciu CTEs. Jednak wątpię, że użycie RDBMS do tego będzie dobrze działać. Napisałem artykuł Jak zrobić to samo co we wspomnianym artykule używając natywnej bazy grafów, w tym przypadku Neo4j: sieci społecznościowe w bazie danych: Korzystanie z bazy danych grafów . Inne niż różnice w wydajności, baza danych grafów upraszcza również zadanie, dostarczając Graph API, które ułatwia obsługę przejść, które byłyby bardzo skomplikowane do zapisu w SQL (lub za pomocą procedur składowanych). Trochę więcej na temat baz danych grafów napisałem w ten wątek i zobacz ten też.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:25:16
Bez jakiejś rekurencyjnej procedury składowanej (CTE w SQL Server 2005+), będziesz potrzebował wielu podróży w obie strony, gdy poziomy będą coraz głębsze. Jednak dobra infrastruktura pamięci podręcznej może naprawdę pomóc w wydajności, ponieważ najpopularniejsze / aktywne listy połączeń użytkowników pozostaną w pamięci podręcznej. Mechanizm odczytu/zapisu przez pamięć podręczną sprawi, że będzie jeszcze lepiej (aktualizacje pamięci podręcznej kaskadowo do aktualizacji db, odczyt pamięci podręcznej kaskadowo do odczytów db)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-10-13 05:18:48