アイテム詳細

要旨

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 (\textbf{N}ot \textbf{A}nother \textbf{G}oogle \textbf{A}nswer), 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 (\textbf{S}teiner \textbf{T}ree \textbf{A}pproximation in \textbf{R}elationship Graphs), an efficient technique
for finding ``close'' relations (i.e., compact connections) between $k(\geq 2)$ entities of interest in large entity-relationship graphs.

Our third contribution is MING (\textbf{M}ining\textbf{In}formative \textbf{G}raphs). MING is an efficient method for retrieving ``informative''
subgraphs for $k(\geq 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 YAGO-NAGA project.