friendster, open BC, kontakte 6. Ebene

[ibekowies at shavingkiwis.de]

Hallo,

Hier ist der Stand der Dinge bei meinem rumprobieren:

ich nehme alle Kontake und deren Kontake und baue daraus ein Tabelle 
mit Triples, also P1->P2->P3, wobei die ID von P1 hier kleiner als 
die von P3 ist, damit ich nur ein richtung speichern und abfragen 
muss.

Diese Tabelle ist etwa 700MB gross pro 50.000 personen mit je 
durchschnittlich 15 Kontakten (inkl. Indizes)

Um eine 6er Verbindung herauszufinden kann ich einfach diese Tabelle 
3 mal self-joinen.
Also:

P1 P2 P3 [erstes Triple]
join ueber P3
P3 P4 P5 [zweites Triple]
join ueber P5
P5 P6 P7 [drittes Triple]

P1 wird auf die Start-Person gematched
P7 wird auf die End-Person gematched

Wobei Startperson die mit der niedrigeren ID ist.


Puh.

Eigentlich waere das sehr performant, da von Triple 1 aus nur 
'durchschn. Kontakte hoch 2' Zeilen gejoined werden muessen und von 
Triple 3 aus (von hinten sozusagen) ebenfalls.

Jetzt ist es eigentlich nur noch eine Frage, ob ich die Indizes so 
setzen und nutzen kann, das MySQL das hinbekommt ohne Full Table 
Scans.


explain SELECT c1.p2, c1.p3, c2.p2, c2.p3, c3.p2 FROM contacts3 c1, 
contacts3 c2, contacts3 c3 WHERE c1.p1 = 3084 AND c1.p3 = c2.p1 AND 
c2.p3 = c3.p1 AND c3.p3 = 3122;
+-------+------+---------------+------+---------+-------+------+-------------------------+
| table | type | possible_keys | key  | key_len | ref   | rows | Extra                   |
+-------+------+---------------+------+---------+-------+------+-------------------------+
| c1    | ref  | p1            | p1   |       4 | const |   71 | where used; Using index |
| c2    | ref  | p1            | p1   |       4 | c1.p3 |  588 | Using index             |
| c3    | ref  | p1            | p1   |       4 | c2.p3 |  588 | where used; Using index |
+-------+------+---------------+------+---------+-------+------+-------------------------+

588 muesste hier die anzahl der Bekannten der Ebene 2 sein (Also die Freunde meiner Freunde), dieser Wert duerfte also nicht steigen...




Viele Gruesse ersteinmal, ILja


On 8 Feb 2005 at 8:39, Sebastian Mendel wrote:

> ibekowies at shavingkiwis.de schrieb:
> 
> > Tabelle Personen
> > Tabelle Kontakte (Person A kennt Person B)
> > 
> > Query:
> > Finde den kuerzesten Pfad von A nach F (und moeglichst performant)
> > Also A kennt B, B kennt C, C kennt D ... E kennt F
> 
> ich glaube dein Problem heißt: "Numbering Paths" oder "der kürzeste Weg"
> und die Lösung eventuell "Dijkstra-Algorithmus" oder "LC-Algorithmen" 
> (Food/Moor, Floyd/Warshall, Kleene/Warshall, ...)
> 
> http://www.informatik.uni-freiburg.de/~zupancic/docus/dijkstra.html
> http://dsor.upb.de/vawi/11_kuerzeste_wege/
> 
> 
> 
> der Vorteil bei dir ist, und was zu beachten wäre, ist das deine Wege 
> zwischen den Knoten immer exakt 1 betragen.
> 
> viel Spaß beim rumprobieren
> 
> -- 
> Sebastian Mendel
> 
> www.sebastianmendel.de www.warzonez.de www.tekkno4u.de www.nofetish.com
> www.sf.net/projects/phpdatetime        www.sf.net/projects/phptimesheet
> 
> -- 
> Infos zur Mailingliste, zur Teilnahme und zum An- und Abmelden unter
> -->>  http://www.4t2.com/mysql 
> 
> 


-- 
Infos zur Mailingliste, zur Teilnahme und zum An- und Abmelden unter
-->>  http://www.4t2.com/mysql