SciDok

Eingang zum Volltext in SciDok

Lizenz

Dissertation zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-29649
URL: http://scidok.sulb.uni-saarland.de/volltexte/2010/2964/


Searching and ranking in entity-relationship graphs

Kasneci, Gjergji

pdf-Format:
Dokument 1.pdf (1.822 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: World Wide Web , Entity-Relationship-Datenmodell , Graph , Information Retrieval , Suchmaschine , Semantik , Ranking
Freie Schlagwörter (Deutsch): Internet , Entity-Relationship-Graph , Subgraph-Matching-Technik , NAGA , STAR , MING
Freie Schlagwörter (Englisch): World Wide Web , search engine , entity-relationship graph , ranking , semantics
Institut: Fachrichtung 6.2 - Informatik
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Hauptberichter: Weikum, Gerhard (Prof. Dr.-Ing.)
Sprache: Englisch
Tag der mündlichen Prüfung: 21.12.2009
Erstellungsjahr: 2009
Publikationsdatum: 06.05.2010
Kurzfassung auf Englisch: The Web bears the potential to become the world';s most comprehensive knowledge base. Organizing information from the Web into entity-relationship graph structures could be a first step towards unleashing this potential. In a second step, the inherent semantics of such structures would have to be exploited by expressive search techniques that go beyond today';s keyword search paradigm. In this realm, as a first contribution of this thesis, we present NAGA (Not Another Google Answer), a new semantic search engine. NAGA provides an expressive, graph-based query language that enables queries with entities and relationships. The results are retrieved based on subgraph matching techniques and ranked by means of a statistical ranking model. As a second contribution, we present STAR (Steiner Tree Approximation in Relationship Graphs), an efficient technique for finding "close'; relations (i.e., compact connections) between k(> 2) entities of interest in large entity-relationship graphs. Our third contribution is MING (Mining Informative Graphs). MING is an efficient method for retrieving "informative'; subgraphs for k(> 2) entities of interest from an entity-relationship graph. Intuitively, these would be subgraphs that can explain the relations between the k entities of interest. The knowledge discovery tasks supported by MING have a stronger semantic flavor than the ones supported by STAR. STAR and MING are integrated into the query answering component of the NAGA engine. NAGA itself is a fully implemented prototype system and is part of the YAGONAGA project.
Kurzfassung auf Deutsch: Das Web birgt in sich das Potential zur umfangreichsten Wissensbasis der Welt zu werden. Das Organisieren der Information aus dem Web in Entity-Relationship-Graphstrukturen könnte ein erster Schritt sein, um dieses Potential zu entfalten. In einem zweiten Schritt müssten ausdrucksstarke Suchtechniken entwickelt werden, die über das heutige Keyword-basierte Suchparadigma hinausgehen und die inhärente Semantik solcher Strukturen ausnutzen. In diesem Rahmen stellen wir als ersten Beitrag dieser Arbeit NAGA (Not Another Google Answer) vor, eine neue semantische Suchmaschine. NAGA bietet eine ausdrucksstarke, graphbasierte Anfragesprache, die Anfragen mit Entitäten und Relationen ermöglicht. Die Ergebnisse werden durch Subgraph-Matching-Techniken gefunden und mithilfe eines statistischen Modells in eine Rangliste gebracht. Als zweiten Beitrag stellen wir STAR (Steiner Tree Approximation in Relationship Graphs) vor, eine effiziente Technik, um "nahe'; Relationen (d.h. kompakte Verbindungen) zwischen k(> 2) Entitäten in großen Entity-Relationship-Graphen zu finden. Unser dritter Beitrag ist MING (Mining Informative Graphs). MING ist eine effiziente Methode, die das Finden von "informativen'; Subgraphen für k(> 2) Entitäten aus einem Entity-Relationship-Graphen ermöglicht. Dies sind Subgraphen, die die Beziehungen zwischen den k Entitäten erklären können. Im Vergleich zu STAR unterstützt MING Aufgaben der Wissensexploration, die einen stärkeren semantischen Charakter haben. Sowohl STAR als auch MING sind in die Query-Answering-Komponente der NAGA-Suchmaschine integriert. NAGA selbst ist ein vollständig implementiertes Prototypsystem und Teil des YAGO-NAGA-Projekts.
Lizenz: Standard-Veröffentlichungsvertrag

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English