Un modo efficace per implementare LinkedIn come la funzionalità "Come sei connesso a"?

Question

LinkedIn ha questa interessante funzionalità in cui durante la visita del profilo di un utente, LinkedIn richiede come ci si connette a quell'utente attraverso la rete.

Supponendo che il visitatore e il proprietario del profilo siano due nodi di un grafico in cui i nodi rappresentano gli utenti e il bordo rappresenta l'amicizia, una soluzione semplice potrebbe essere un bfs che inizia da entrambi i nodi fino a un certo livello e vedere se ci sono intersezioni. Le intersezioni sarebbero i nodi di collegamento di rete.

Anche se questo sembra accurato, il problema è che per determinare gli amici di ogni persona è necessaria una query DB separata. Quando la rete supera i 2 livelli, sarebbe un algoritmo molto dispendioso in termini di tempo. Esiste un'alternativa più efficiente? In caso contrario, come possiamo aggiungere un migliore supporto hardware (calcolo parallelo, griglie, database distribuito, ecc.) Per ridurre il tempo richiesto per il calcolo?

Answer 1

Si può vedere come questo può essere fatto nell'articolo Graphs in the database: SQL meets social networks di Lorenzo Alberton. Il codice di esempio è scritto per PostgreSQL usando CTE. Tuttavia, dubito che l'utilizzo di un RDBMS per questo avrà un buon rendimento. Ho scritto un articolo su come fare le stesse cose come nell'articolo menzionato utilizzando un database grafico nativo, in questo caso Neo4j: Social networks in the database: using a graph database. A parte le differenze nelle prestazioni, un database grafico semplifica anche l'attività fornendo un'API di grafico che semplifica la gestione di attraversamenti che sarebbero estremamente complessi da scrivere in SQL (o utilizzando stored procedure). Ho scritto un po 'di più sui database di grafici in this thread e vedere anche this one.

Answer 2

Senza una sorta di procedura memorizzata ricorsiva (CTE in SQL Server 2005+), avrete bisogno di più round trip mentre i livelli si approfondiscono. Tuttavia, una buona infrastruttura cache potrebbe davvero aiutare le prestazioni poiché gli elenchi di connessioni degli utenti più popolari/attivi resterebbero nella cache. Un meccanismo di lettura/scrittura tramite cache renderebbe le cose ancora migliori (gli aggiornamenti della cache si sovrappongono agli aggiornamenti DB, le letture cache in cascata alle letture db)