Wie können Websites wie LinkedIn die Beziehung der ersten/zweiten/dritten Ebene neben dem Namen einer Person anzeigen?

Question

Ich habe vor kurzem ein Vorstellungsgespräch verpatzt, indem ich eine einfache Frage schlecht beantwortete: Wie zeigen Seiten wie LinkedIn effizient die Beziehungsdistanz (1./2./3.) Von Ihnen zu jeder auf einer Seite angezeigten Person (zB in Personensuchergebnissen, Liste von Menschen, die in einer Firma arbeiten, etc.)?

<EDIT> habe ich das Wesentliche „Trick“ der Lösung: finding „von mir Abstand“ ist eine gemeinsame Operation (zB 20x + auf einer einzigen Seite 100 Pro-Login-Sitzung), so dass Sie Teil tun können die "Entfernung von mir zu X", cache sie und verwende dann das zwischengespeicherte Teilergebnis mehrmals, um andere Operationen viel billiger zu machen. Ich vermutete auch, dass das Teilergebnis wahrscheinlich meine Verbindungen auf der zweiten Ebene sein würden, weil "alle Verbindungen auf der dritten Ebene zwischenspeichern" im RAM und der CPU zu teuer wären. </EDIT >

Aber wenn diese Einsicht in eine Lösung zu konvertieren versuchen, kam ich mit einem unbeholfenen Antwort auf die Schaffung beinhaltet andauerndes Caches von 2nd-Level-Verbindungen von jeder auf der Website (die enorm epensive gewesen wäre, in perf und komplex zu halten), und ich nahm einen unerklärlichen Umweg, Bloom Filters in einer Weise zu verwenden, die wenig technischen Sinn machte. Ich hätte mich nach einer solchen Antwort nicht angestellt!

Später, als ich über das Problem ohne den Druck eines Interviews über meinen Kopf dachte, kam ich eine vernünftigere Antwort.

• Erstellen Sie eine sehr schnelle Art und Weise, die First-Level-Verbindungen für jede Charge von Benutzer-IDs zu erhalten (Losgröße bis zu ~ 1000?). Dies bedeutet wahrscheinlich einen dedizierten Cluster von Lots-of-RAM-Servern, die die Verbindungen des 1. Netzwerks des gesamten Netzwerks im Speicher zwischenspeichern können. Zum Glück, 50M Mitglieder x durchschn. 100 Verbindungen pro Mitglied x 4 Bytes pro Mitglied ID = < 25 GB im RAM zwischenspeichern, was mit preiswerter Hardware machbar ist. Und die Anzahl der Änderungen pro Tag wird unter 1% liegen, also ist es nicht zu schwer, den Cache auf dem neuesten Stand zu halten. (Beachten Sie, dass eine relationale Datenbank wahrscheinlich eine schlechte Wahl ist, um diesen Cache zu implementieren, da das Zugriffsmuster "Lose zufälliger E/A" die relationale DB-Leistung zerstört.)

• Wenn ein Benutzer sich anmeldet, wird seine 2. Ebene zwischengespeichert Verbindungen durch Abrufen der Verbindungen der 1. Ebene jeder Verbindung der 1. Ebene und Einstecken einer Hashtabelle (Schlüssel = ID der 2. Ebene, Wert = Array der Verbindungen der 1. Ebene, die Sie verbinden). Zwischenspeichern Sie auch die Verbindungen der ersten Ebene, so dass Sie die 1. und 2. Ebene über einen einzigen Anruf zurück auf Ihren Remote-Cacheserver ziehen können. Benutzer-IDs können leicht partitioniert werden, so dass ein verteilter Cache wie Memcached dafür gut funktionieren kann.

• für jede Benutzer-ID, um herauszufinden, ob es in Ihrem „Netzwerk“ ist und welche Beziehung es zu Ihnen ist (1., 2., 3.), gehen Sie wie folgt vor:

  1. , wenn die ID in Ihr First-Level-Verbindungen, zu stoppen.
  2. versuchen Sie, die ID in Ihren zwischengespeicherten 2nd-Level-Verbindungen Hashtable nachschlagen. Falls gefunden, gebe das Array der Verbindungen zurück, die dich verbinden.
  3. holen Sie die Verbindungen der ersten Ebene der ID, und wiederholen Sie Schritt # 2 für jede von ihnen. Alle Ergebnisse in einem einzigen Array zusammenfassen und zurückgeben.
  4. <EDIT> Refactoring in eine Batch-Implementierung („von mir aufblicken Abstand zu N verschiedene Benutzer“), so können Sie alle Remote-Ergebnisse von Schritt # 3, ohne dass N Ferngespräche machen zu bekommen.</EDIT >

Aber ich bin sicher, es gibt bessere Antworten. Welches ist deines? Wenn Sie eine zusätzliche Herausforderung haben möchten, versuchen Sie es mit einer Simulation der Situation (können keine Lösungen im Internet finden).

Beachten Sie, dass die Frage war eine optimale Lösung, unabhängig von how LinkedIn actually does it today, die ich nach oben sah, nachdem ich meine eigene Antwort oben geschrieben.

Answer 1

Sie können möglicherweise Axiome über small world networks nutzen, um diese Art von Traversierung zu optimieren.

Kleine Weltnetze sind durch "Hubs" gekennzeichnet, die sehr dichte Verbindungen anderer Knoten darstellen. Die meisten Knoten im Netzwerk verbinden sich im Allgemeinen entweder innerhalb weniger Hops mit einem topologisch nahe gelegenen Knoten (1-4 Hops entfernt) oder werden durch einen oder mehrere solcher Hubs routen. Dies ist einer der Hauptgründe dafür, dass sich kleine Weltnetzwerke so verhalten, wie sie es tun.

Answer 2

Wenn Sie darüber nachdenken, könnte dies in SQL sehr prozessorintensiv sein.

Angesichts dieser Tatsache und der Tatsache, dass es schließlich überall verwendet wird, und dieser Raum ist relativ billig ... Ich würde vorschlagen, einen Index mit Lucene (oder Lucene.NET) abhängig von Ihrer bevorzugten Sprache erstellen. Sie könnten so ein paar Dinge tun.

Sie können entweder eine Strukturtyp-Datenstruktur erstellen und Ihren Index rekursiv durchsuchen, indem Sie nach allen übergeordneten Knoten oder untergeordneten Knoten und ihren übergeordneten oder untergeordneten Knoten suchen, je nach Ihren aktuellen Anforderungen.

Oder Sie könnten alle Beziehungen schreiben, wie sie erstellt werden (der Raum ist billig Konzept). Dies wäre ein einmaliger Schreibvorgang (den Sie nicht so oft aktualisieren würden). Wenn eine Beziehung erstellt oder widerrufen wird, würden Sie eine Aktualisierung für Ihren Index in die Warteschlange stellen (Warteschlange, weil Sie nicht für den Schreibvorgang für einzelne Anfragen geöffnet werden möchten ... Batch-Index-Updates). Dann könnten Sie diese wirklich flache Struktur lesen, um die fraglichen IDs zu erhalten.

Mit den IDs in der Hand (von denen jemals Such-Typ durchführen) können Sie dann in die DB gehen, um die umliegenden erforderlichen Informationen zu erhalten. Dann cache deine Ausgabe, um weiter zu minimieren, was eine sehr schnelle Suche, DB-Abfrage, Datenaufbau ... wäre, aber noch schneller, wenn sie nur aus dem Cache kommt.

Verwenden Sie Velocity, MemCached oder MemCached Win32 für das zentralisierte Caching über eine Webfarm.

Answer 3

Interessanterweise würde die Technologie von 1970 eine gute Arbeit leisten, dies zu modellieren. Die Network Database Model verwaltet diese Art von Beziehung effizient.

Es ist nicht effizient in Bezug auf Ad-hoc-Abfragen oder Datenmodell-Wartung, so fiel mit dem Anstieg der relationalen Datenmodelle in Ungnade.

Answer 4

Ich bin die Tabellenstruktur nicht sicher, oder die Komplexität des Systems, aber hier ist ein einfaches SQL Server Beispiel eines rekursiven CTE mit:

DECLARE @People table (PersonID int, Name varchar(10)) 
DECLARE @Network table (PersonID int, NetworkedPersonID int) 
INSERT INTO @People VALUES (1,'AAA') 
INSERT INTO @People VALUES (2,'BBB') 
INSERT INTO @People VALUES (3,'CCC') 
INSERT INTO @People VALUES (4,'DDD') 
INSERT INTO @People VALUES (5,'EEE') 
INSERT INTO @People VALUES (6,'FFF') 
INSERT INTO @People VALUES (7,'GGG') 
INSERT INTO @People VALUES (8,'HHH') 
INSERT INTO @Network VALUES (1,2) 
INSERT INTO @Network VALUES (1,3) 
INSERT INTO @Network VALUES (2,5) 
INSERT INTO @Network VALUES (2,7) 
INSERT INTO @Network VALUES (4,8) 
INSERT INTO @Network VALUES (7,8) 
INSERT INTO @Network VALUES (7,3) 
INSERT INTO @Network VALUES (8,9) 
DECLARE @TargetPersonID int 
SET @TargetPersonID=1 

;WITH NetworkLevels AS 
( SELECT 
     NetworkedPersonID,1 AS NetworkLevel 
     FROM @Network 
     WHERE PersonID=@TargetPersonID 
    UNION ALL 
    SELECT 
     n.NetworkedPersonID, l.NetworkLevel+1 
     FROM @Network    n 
      INNER JOIN NetworkLevels l ON n.PersonID=l.NetworkedPersonID 
    WHERE l.NetworkLevel<=2 
) 
SELECT * FROM NetworkLevels 

OUTPUT:

NetworkedPersonID NetworkLevel 
----------------- ------------ 
2     1 
3     1 
5     2 
7     2 
8     3 
3     3 

(6 row(s) affected) 

Answer 5

Isn 't linkedin Daten als ein großes riesiges Diagramm dargestellt?und wenn sich eine Person anmeldet, würde das System Handle zu seinem Knoten haben, und dann, indem Breite zuerst Traversal für 3 Ebenen, das System würde diese Knoten als Set (zusammen mit welcher Level-Info) und wenn eine Person auf der Webseite erscheint , sucht das System auf diesem Knotensatz und gibt den Beziehungsabstand aus.

Dies ist meine Vermutung. Bitte zögern Sie nicht, darauf hinzuweisen, was es unpraktisch macht.

Answer 6

Um

DistanceCategory(A,B): { 1, 2, 3+} 

Verwenden Tatsache zu implementieren, dass Verbindungen bidirektional sind.

Shop 1. Ebene Verbindungen als sortierte Liste in einigen KV wund:

Key: [UserFromId,UserToId]. 
Value: UserToId 

Pseudocode:

DistanceCategory(A,B) 
{ 
    if (exists([A,B])) 
     return 1; 
    if (firstCommonElement(getAll([A,B]), getAll([A,B])) != null) 
     return 2; 
    return 3; 
} 

Komplexität: O (C1 + C2). C1, C2 - Anzahl der Verbindungen beider Benutzer.