Graphensuche auf Grundlage von strukturellen Merkmalen Jonathan Hellwig 19.02.2008 Indizieren und Anfragen von Graphen in Datenbanken Silke Trißl

Graphensuche auf Grundlage von strukturellen MerkmalenJonathan Hellwig19.02.2008

Indizieren und Anfragen von Graphen in DatenbankenSilke Trißl

2Jonathan Hellwig – Graphensuche auf Grundlage von strukturellen MerkmalenSilke Trißl - Indizieren und Anfragen von Graphen in Datenbanken

Gliederung

• Einführung• Graphenanfrage• Indizierung

• Indizierung mit Strukturmerkmalen• Häufige Merkmale• Diskriminierende Merkmale

• Konstruktion des Indizes und Suche• gIndex vs. GraphGrep• Diskussion


Graphen

• Ein Graph ist ein Tupel (V,E).• Graphen eignen sich um komplexe

Strukturen, wie chemische Verbindungen, soziale Netzwerke oder Verkehrsnetze darzustellen.


Arten von Graphen

• Es gibt verschiedene Arten von Graphen:• Graphen in denen die Knoten und Kanten Label

haben.• Graphen in denen die Kanten eine Richtung

haben.• Nach ihrer Struktur:

• z. B. planare Graphen, Bäume, Pfade, vollständige Graphen und Chordalgraphen.

• Wir interessieren uns für einfache Graphen mit gelabelten Knoten.


Graphendatenbank

• Mit Hilfe von DB kann man Graphen effizient speichern.

• Als Anwender muss man sich nicht darum kümmern, wo und wie die Graphen gespeichert sind.


Beispiele für Graphen = unsere Datenbank


Subgraphen

• H=(W,F) ist ein Subgraph von G=(V,E) wenn:• W ist eine Teilmenge von V• F ist eine Teilmenge von E


Subgraphen


Graphenanfrage

• Eingabe: ein Graph G• Ausgabe: alle Graphen der DB, die G als

Subgraphen haben

10

Jonathan Hellwig – Graphensuche auf Grundlage von strukturellen MerkmalenSilke Trißl - Indizieren und Anfragen von Graphen in Datenbanken

Graphenanfrage

11


Graphenanfrage auf indizierte Datenbank

• Um schneller auf Graphen zuzugreifen bietet sich die Bildung eines Indizes an.• Anhand der Merkmale der Graphen wird ein

Index erstellt.• Jeder Indexeintrag (Merkmal) enthält eine Liste

der Graphen, die Indexmerkmal erfüllen.

12



• Bei einer Anfrage:• Wird aus dem Index eine Kandidatenliste

erstellt.• Kandidatenliste ist viel kleiner und kann

schneller nach dem endgültigem Ergebnis durchsucht werden.

13



14


Indizierung mit GraphGrep

• Indizierungsmerkmal sind Pfade.• Dabei werden nicht alle Pfade gewählt,

sondern nur Pfade bis zu einer bestimmten Länge.

15



• Vorteile:• Begrenzter Indexraum.• Pfade sind einfach zu manipulieren.

• Nachteile:• Strukturelle Informationen können verloren

gehen.• Index sehr groß werden.

16



17


Gliederung


• Indizierung mit StrukturmerkmalenIndizierung mit Strukturmerkmalen• Häufige Merkmale• Diskriminierende Merkmale

• Konstruktion des Indizes und Suche• gIndex vs. GraphGrep• Diskussion

18


Indizierung mit Strukturmerkmalen

• Indizierungsmerkmal sind Subgraphen.• Vorteil:

• Strukturmerkmale bleiben erhalten.

• Nachteil:• Sehr viele Subgraphen.

19



• Vorgestellte Methode: gIndex• Es werden nicht alle Subgraphen gewählt

sondern nur solche die:• Häufig in der Datenbank vorkommen, d. h. in

vielen Graphen der Datenbank enthalten sind.• Diskriminativ in Bezug auf die schon im Index

enthaltenen Merkmale sind.

20


Häufige Merkmale

• Häufige Merkmale sind solche die in vielen Graphen der Datenbank enthalten sind.

• Formal ausgedrückt:• Für ein Merkmal (Graph) ist Sup(m) (Support)

ist die Anzahl der Graphen in der DB in denen m ein Subgraph ist.

• minSup ist die minimale Häufigkeit, die ein Merkmal haben muss um als häufig zu gelten.

• Alle Graphen m mit Sup(m)≥ minSup werden im Index aufgenommen.

21


Häufige Merkmale

• Warum häufige Merkmale?• Um Indexgröße zu beschränken.

• (minSup = 1 oder minSup = |DB|)

• Vorteile bei großem minSup:• Kleiner Index.

• Vorteile bei kleinem minSup:• Kleine Kandidatenliste.

22


Häufige Merkmale

• Es könnte vorkommen, dass Graphen keine häufigen Merkmale haben und deshalb nicht vom Index überdeckt werden.

• Lösung:• Es wird kein statisches minSup gewählt,

sondern als eine monoton wachsenden Funktion abhängig von der Kantezahl der Merkmale.

23


Häufige Merkmale

Größe des Merkmals (Zahl der Kanten)

Häufigkeit des Merkmals in DB

5 10

1

5

10

•Kleine Subgraphen werden immer gewählt.

•Große Subgraphen werden nur gewählt, wenn sie oft vorkommen.

24


Häufige Merkmale

25


Diskriminierende Merkmale

• Diskriminierende Merkmale werden in Bezug auf die schon im Index enthaltenen Merkmale betrachtet.

• Ein Merkmal ist diskriminierend, wenn es die Graphen in der DB besser unterscheidet als die schon im Index enthaltenen Merkmale.

• Dadurch kann die Größe des Indizes reduziert werden.

26


Diskriminierende Merkmale (Formal)

• Seien m1,…, mk die Subgraphen von einem Merkmal m, die bereits im Index enthalten sind.

• Da im Index immer der leere Graph Ø enthalten ist, gibt es mindestens ein mi.

• Dm sind die Graphen der Datenbank, die m enthalten. • Folgende Formel beschreibt wie diskriminierend ein

Merkmal m ist.

• Alle Merkmale mit γ größer als γmin werden in den Index aufgenommen.

27



28



29


Gliederung


• Indizierung mit Strukturmerkmalen• Häufige Merkmale• Diskriminierende Merkmale

• Konstruktion des Indizes und SucheKonstruktion des Indizes und Suche• gIndex vs. GraphGrep• Diskussion

30


Konstruktion des Indizes

• Zur Bildung des Indizes werden alle Merkmale (Subgraphen) der Graphen aus der Datenbank betrachtet.

• Der Index wird klein gehalten in dem nur Merkmalen die häufig und diskriminierend sind aufgenommen werden.

• Durch die monoton steigende Häufigkeit wird gewährleistet, dass der Index alle Graphen der DB abdeckt.

31


Konstruktion des Indizes

• Als Eingabe brauch man:• Graphen-DB, minSup Funktion,

Diskriminierungsgrad, maximale Größe der Subgraphen maxL.

• Alle Subgraphen bis Größe maxL werden in aufsteigender Größe betrachtet.

• Ist ein Subgraph häufig und diskriminierend wird er im Index aufgenommen.

32


Suche der Graphen

• Alle Subgraphen der Anfrage werden betrachtet.

• Merken welche Subgraphen in Merkmalsliste sind

• Schnittmenge aller gemerkten Subgraphen ist Kandidatenliste

33



34


Einfügen und Löschen von Graphen

• Bei einer Datenbank üblich:• Informationen hinzufügen.• Informationen löschen.

• Wunsch: Indexkonstruktion nicht zu wiederholen.• Merkmalsliste nicht ändern.

35


Einfügen und Löschen von Graphen G

• Einfügen von G:• Subgraphen von G betrachten, die bereits im

Indexeinträgen sind.• G zu diesen Indexeinträgen hinzufügen.

• Löschen von G:• Subgraphen von G betrachten, die

Indexeinträgen sind.• G von diesen Indexeinträgen löschen.

36


gIndex vs. GraphGrep

• Die Datensätze• Realer Datensatz:

• Chemische Verbindungen.• 43.905 Moleküle (Stand März 2002).

• Syntetischer Datensatz mit folgenden Parametern:• Größe der Datenbank.• Durchschnittsgröße der Graphen.• Anzahl der Labels.

37



38



39


Diskussion

• Kiritik:• Authoren des Papers sagen, dass sie besser als

GraphGrep sind.• Nur unter bestimmten Bedingungen:

• Wenige Labels.• Struktur der Graphen keine Pfade.

• Keine anderen Vergleiche außer mit GraphGrep.

40


Diskussion

• Positiv:• Gut organisiertes Paper.• Neue (innovative) Methode.• Damals die schnellsten.

41


Diskussion

• Ideen zur Optimierung:• Index verbessern.

• z. B. fertigen Index noch mal auf nicht diskriminierende Merkmale prüfen.

• Ausrichtung auf bestimmte Typen von Graphen.• z. B. durch Parametrisierung.

Documents

Graphensuche auf Grundlage von strukturellen Merkmalen Jonathan Hellwig 19.02.2008 Indizieren und Anfragen von Graphen in Datenbanken Silke Trißl