Kürzeste Wege im Wikipedia-Linkgraph

dc.contributor.authorKara, Ferdide
dc.date.accessioned2013-05-13de
dc.date.accessioned2016-03-31T08:00:22Z
dc.date.available2013-05-13de
dc.date.available2016-03-31T08:00:22Z
dc.date.issued2013de
dc.description.abstractDiese Arbeit beschäftigt sich mit unterschiedlichen Beschleunigungstechniken zur Suche kürzester Pfade in einem Graph. Im Gegensatz zu klassischen Weganfragen wird jedoch kein geographischer Graph als Datenquelle genutzt, sondern der manuell extrahierte Wikipedia-Linkgraph. Um eine Vergleichsgrundlage für Beschleunigungsalgorithmen zu erhalten, wird eine Auswertung der Breitensuche als Basis geschaffen. Zur optimalen Auswahl eines Beschleunigungsalgorithmus ist es unabdingbar, ein grundlegendes Verständnis über die Struktur des Graphen zu erhalten. In Folge dieser Untersuchung und einer Vorstellung unterschiedlicher Beschleunigungsalgorithmen wird das Transitknotenkonzept, welches in der Arbeit von Bast u.a. [BFM+07] vorgestellt wurde, auf den Wikipedia-Linkgraph angewandt. Um das Konzept auf einen nicht geographischen Graph anwenden zu können, wird nach der Arbeit von Eisner/Funke [EF12] die Suche nach einer passenden Transitknotenmenge als Hitting-Set-Problem formuliert. Die Qualität der ausgewählten Transitknoten wird mit unterschiedlichen Konstruktionen zur Transitknotenbestimmung verglichen und die verschiedenen Lösungen werden anhand der vorhergehenden Untersuchung der Graphstruktur erklärt. Schlussendlich wird gezeigt, warum die verschiedenen Konstruktionen der Transitknotenmenge schlechte Ergebnisse liefern, wodurch das Transitknotenkonzept angewandt auf den Wikipedia-Linkgraph fehlschlägt.de
dc.identifier.other382464338de
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:bsz:93-opus-83928de
dc.identifier.urihttp://elib.uni-stuttgart.de/handle/11682/3067
dc.identifier.urihttp://dx.doi.org/10.18419/opus-3050
dc.language.isodede
dc.rightsinfo:eu-repo/semantics/openAccessde
dc.subject.ddc004de
dc.titleKürzeste Wege im Wikipedia-Linkgraphde
dc.typemasterThesisde
ubs.fakultaetFakultät Informatik, Elektrotechnik und Informationstechnikde
ubs.institutInstitut für Formale Methoden der Informatikde
ubs.opusid8392de
ubs.publikation.typAbschlussarbeit (Diplom)de

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
DIP_3410.pdf
Size:
1.22 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
935 B
Format:
Plain Text
Description: