Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hülle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de

  • Published on
    05-Apr-2015

  • View
    105

  • Download
    1

Embed Size (px)

Transcript

  • Folie 1
  • Seminar Indizieren und Anfragen von Graphen in Datenbanken WS 2007/2008 Thema Transitive Hlle mit geometrischem Ansatz Habib Muhammad Shakhawat shakhawa@informatik.hu-berlin.de
  • Folie 2
  • 2 Transitive Hlle mit geometrischem Ansatz bersicht Motivation Ziel definieren Mgliche Probleme Graphentheoretische Definitionen Kurzer berblick in bisherige Lsungen Vorschlag mit geometrischem Ansatz Leistungsvergleich
  • Folie 3
  • 3 Transitive Hlle mit geometrischem Ansatz Motivation Daten als gerichteter Graph Bio-Informatik Semantic Web Computer Vision usw. Hauptaufgabe einer Datenbank besteht darin die Beziehungen zwischen verschiedene Datenobjekte zu finden und analysieren.
  • Folie 4
  • 4 Transitive Hlle mit geometrischem Ansatz Motivation u und v sind zwei Datenobjekte Stehen u und v in einer Beziehung ?
  • Folie 5
  • 5 Transitive Hlle mit geometrischem Ansatz Zielformulierung Gegeben Ein gerichteter Graph G = (V,E) u, v V Ziel: Schnelle Antwort auf der Frage Gibt es einen Pfad von u nach v in G?
  • Folie 6
  • 6 Transitive Hlle mit geometrischem Ansatz Wo sind die Probleme ? Erreichbarkeitsinformation ber den gesamten Graph notwendig Reale Graphen sind gro Preprocessing notwendig Hhe Speicher- und Zeitbedarf
  • Folie 7
  • 7 Transitive Hlle mit geometrischem Ansatz Einige Definitionen Graph: Ein Graph G=(V,E) besteht aus eine endliche Menge von Knoten V und Kanten E. 0 12 34 Ungerichtet G Gerichtet 0 12 34
  • Folie 8
  • 8 Transitive Hlle mit geometrischem Ansatz Einige Definitionen Pfad: Ein Weg indem kein Knoten mehrfach vorkommt. Kreis: Ein geschlossener Kantenzug, in dem kein Knoten mehrfach vorkommt. Starke Zusammenhangskomponente (SZK): Fr jede bel. u und v in V gilt: es ex. ein Pfad aus u nach v in G. 0 12 34 0 12 34 0 12 34 5
  • Folie 9
  • 9 Transitive Hlle mit geometrischem Ansatz Einige Definitionen Transitive Hlle: H(G)=(V, E) ist transitive Hlle von G=(V, E) gdw. E={(u,v)|u,v V und Pfad von v nach w in E} 0 12 34 10111 11111 00111 00111 00111 n x n Erreichbarkeitsmatrix Nach Von
  • Folie 10
  • 10 Transitive Hlle mit geometrischem Ansatz Einige Definitionen Problematik bei Transitive Hlle Sehr hoher Zeitaufwand bei der Berechnung Warshall Sehr hoher Speicherbedarf Worst-Case
  • Folie 11
  • 11 Transitive Hlle mit geometrischem Ansatz Kurzer berblick: Bisherige Lsungen 2-hop cover (Cohen et al, 2002) Pfade als Konkatenation je zweier Pfadteilstcke zu reprsentieren Teilstcke werden an so genannten Hop Knoten zusammengefgt C = Hop-Knoten abcdef
  • Folie 12
  • 12 Transitive Hlle mit geometrischem Ansatz Kurzer berblick: Bisherige Lsungen Beispiel: 2-hop cover ac bc cc abcdef cc cd ce cf ac ad ae af bc bd be bb cc cd ce cf c in = c out berdeckte Kanten in TC
  • Folie 13
  • 13 Transitive Hlle mit geometrischem Ansatz Kurzer berblick: Bisherige Lsungen Vorteil: 2-Hop Cover Statt der ganzen transitiven Hlle speichert man nur die Pfade zu den Hop-Knoten Gre der 2-hop cover ist kleiner als die Transitive Hlle Antwortzeiten sind konstant
  • Folie 14
  • 14 Transitive Hlle mit geometrischem Ansatz Kurzer berblick: Bisherige Lsungen Nachteile: 2-Hop Cover Transitive Hlle muss vor der berdeckung durch Hop-Knoten zunchst vollstndig materialisiert werden - Transitive Hlle als Grundmenge fr 2-hop cover Schlechte Laufzeit bei der Berechnung der Hop-Knoten
  • Folie 15
  • 15 Transitive Hlle mit geometrischem Ansatz Kurzer berblick: Bisherige Lsungen Beispiel: Konstruktionszeit und Speicherbedarf Eingabe: Ein Teilgraph von DBLP mit 344,992,370 Verbindungen System: SUN-Fire 15000 mit 64 Prozessoren und 180 GB RAM Groe 2-hop cover: 1,289,930 Eintrge Speicherverbrauch: 80 GB RAM Zeit: 45 Stunden und 23 Minuten
  • Folie 16
  • 16 Transitive Hlle mit geometrischem Ansatz Kurzer berblick: Bisherige Lsungen Wnschenswert Ohne aufwendige Berechnung der Transitive Hlle auszukommen Mglich viele Informationen im Speicher halten
  • Folie 17
  • 17 Transitive Hlle mit geometrischem Ansatz MaxCardinality-G (Cheng et al.) Wnsche werden erfllt durch geometrischen Ansatz nach Cheng et al. Berechnung der Transitive Hlle nicht otwendig Bestimmung der 2-Hop Cover durch Rechteckoperationen Visualisierung der Erreichbarkeitsmatrix durch Rechtecke in einem 2-dim. Gitter
  • Folie 18
  • 18 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G (Cheng et al.) Gegeben: Ein gerichteter Graph G Maxcardinatily-G berechnet 2-Hop Cover in 3 Schritten 1) Konstruiere aus G einen gerichteten kreisfreien Graph G 2) Bestimme 2-Hop Cover fr G 3) Bestimme 2-Hop Cover fr G aus dem 2-Hop Cover von G
  • Folie 19
  • 19 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Konstruktion eines kreisfreien Graph Finde alle starken Zusammenhangs- komponenten (SZK) in G. 0 12 3 7 8 6 4 1 10 5 9 11 G Ersetze SZK mit einen zufllig ausgesuchten Knoten vaus dem SZK Fge alle ein- und ausgehende Kanten von SZK zu vhin. G
  • Folie 20
  • 20 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Konstruktion eines kreisfreien Graph Vorteile: G hat weniger Knoten und Kanten als G (ausgenommen, G hat keine SZK) Mit zunehmender Kantenanzahl steigt die Wahscheinlichkeit der SZK Je mehr SZK desto kleiner ist G Alle Knoten in einem SZK haben den selben Hop-Knoten. Vermeidung unntiger Berechnungen 0 12 3 8 4 1 5 11 9 G
  • Folie 21
  • 21 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Intervall Labeling G wird zerlegt in Spannenden Baum T Nicht-Baumkanten E N Jeder Knoten v in T bekommt min. ein Intervall [s, e] e: Postorder Nummer des Knotens Vergabe bei Postorder Traversal s: Kleinste Postorder Nummer seiner Nachfolger 0 12 3 8 4 1 5 11 9 G 2 5 6 7 4 3 1 9 8 [1,1] [3,3] [3,4] [3,5] [1,6] [7,7] [1,9] [8,8] [2,2]
  • Folie 22
  • 22 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Intervall Labeling Nicht-Baumkanten E N Ist u, v E N, so bekommt u alle Intervalle von v und alle Vorgnger von u ebenso Intervalle knnen zusammengefgt werden. z.B. [5, 9] und [10,15] zusammengefgt in [5, 15] Falls ein Intervall in einem Anderen enthalten ist, kann eliminiert werden 0 12 3 8 4 1 5 11 9 G 2 5 6 7 4 3 1 9 8 [1,1] [3,3] [3,4] [3,5] [1,6] [7,7] [1,9] [8,8] [2,2] [3,3] [1,1] [3,3] [1,1]
  • Folie 23
  • 23 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Reachability Table Konstruiere aus G (V, E ) einen zustzlichen Graph G (V, E ), so dass | V |=| V | (v, u) ist eine Kante in E, falls (u, v) eine Kante in E ist Berechne Postorder Nr. und die Intervall Labels fr G Speichere die Informationen in einer Reachability Table
  • Folie 24
  • 24 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Reachability Table 0 12 3 8 4 1 5 11 9 0 12 9 1 4 8 5 11 3 G G
  • Folie 25
  • 25 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Reachability Map Virtuelle Darstellung der Reachability Table als Reachability Map M durch n x n Gitter x-Achse: Postorder Nr. in G y-Achse: Postorder Nr. in G
  • Folie 26
  • 26 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Reachability Map Wenn po (w) I (v), dann M(po (w), po (v))=true Beispiel: po (9) I (5) M(4,6)=true x
  • Folie 27
  • 27 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Reachability Map Funktion f zuordnet jedes Knotenpaar u, v in G in einer Zelle (x(v), y(u)) in M, wobei x(w)=po (w) - po : Postorder Nr. in G y(w)=po (w) - po : Postorder in G f(u,v) = 1, falls v aus u erreichbar ist, sonst 0 Erreichbarkeit: aus 3 zu 9 f(3,9)=(x(9),y(3))=(4,5)=1 x
  • Folie 28
  • 28 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Algorithmus Algorithmus Schritt 1: Suche max. Flche Von Knoten w Noch nicht berdeckt Schritt 2: w wird neuer Hop-Knoten Erzeuge 2-Hop Labeling fr w Speichere w als Hop-Knoten Schritt 3: Weiter mit Schritt 1, solange w noch vorhanden ist.
  • Folie 29
  • 29 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Algorithmus Konstruktion: Recheck fr w als Hop-Knoten Beispiel: w=1 I (1)=((s 1, e 1 )=[1,1]), (s 2, e 2 )=[3,3]) I (1)=(s 1 , e 1 )=[1,5] Bilde die Rechtecke durch kombinationen aus I (w) und I (w). Rechtecke: ((s1, s 1 ), (e1, e 1 ))=((1,1), (1,5)) ((s2, s 1 ), (e2, e 1 ))=((3,1), (3,5))
  • Folie 30
  • 30 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Rechteckoperationen Rect(B C 1 B C 2 ) = Rect(B C 1 ) Rect(B C 2 )
  • Folie 31
  • 31 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Algorithmus Algorithmus Schritt 1: Suche max. Flche Von Knoten w Noch nicht berdeckt Schritt 2: w wird neuer Hop-Knoten Erzeuge 2-Hop Labeling fr w Speichere w als Hop-Knoten Schritt 3: Weiter mit Schritt 1, solange w noch vorhanden ist.
  • Folie 32
  • 32 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Algorithmus
  • Folie 33
  • 33 Transitive Hlle mit geometrischem Ansatz Maxcardinality-G: Algorithmus Gefundene 2-hop cover 03 59 81 121 08 0 111 31 34 35 39 3 9 0 12 3 8 4 1 5 11 9 InOut 2-hop cover
  • Folie 34
  • 34 Transitive Hlle mit geometrischem Ansatz Leistungsvergleich Fazit: Gefundene 2-hop cover sind hnlich Cohen Cheng Messung am generierten und reale Daten Cohens Algorithmus gegen Chengs
  • Folie 35
  • 35 Transitive Hlle mit geometrischem Ansatz Leistungsvergleich Messung am generierten und reale Daten Cohens Algorithmus gegen Chengs Cohen Cheng Fazit: Chengs Algorithmus ist schneller als Cohens
  • Folie 36
  • 36 Transitive Hlle mit geometrischem Ansatz Literatur Cheng, J., Yu, J.X., Lin, X., Wang, H. & Yu, P.S. Fast Computation of Reachability Labeling for Large Graphs. EDBT Conference 2006 R. Agrawal, A. Borgida, and H. V. Jagadish. Efficient management of transitive relationships in large data and knowledge bases. In Proc. of SIGMOD89, 1989. E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. In Proc. of SODA02, 2002
  • Folie 37
  • 37 Transitive Hlle mit geometrischem Ansatz Fragen ? Danke fr die Aufmerksamkeit

Recommended

View more >