Entity comparison in knowledge graphs
<p>Knowledge graphs (KGs) represent information in a simple, interlinked format and are used in a variety of applications. Besides the standard reasoning tasks such as query answering, there has been an increasing need for new types of analysis. One such fundamental analysis task is entity com...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2019
|
| Subjects: |
| _version_ | 1817932828220850176 |
|---|---|
| author | Petrova, A |
| author2 | Horrocks, I |
| author_facet | Horrocks, I Petrova, A |
| author_sort | Petrova, A |
| collection | OXFORD |
| description | <p>Knowledge graphs (KGs) represent information in a simple, interlinked format and are used in a variety of applications. Besides the standard reasoning tasks such as query answering, there has been an increasing need for new types of analysis. One such fundamental analysis task is entity comparison, i.e., determining what two entities have in common and how they are different. The importance of such a task can be seen in various applications such as product comparisons, and explainable recommender systems. This thesis studies the problem of entity comparison over knowledge graphs and presents a novel framework that models comparisons via similarity and difference queries. It is the first declarative comparison framework for linked data that treats both similarities and differences as first-class citizens.</p>
<p>We first define the syntax and semantics of various types of comparison queries, motivating each type with examples and establishing important relations between different query types. Next, we study the complexity of the two fundamental decision problems over queries, namely the existence and verification problems, for basic comparison queries and for most specific similarity queries (MSSQs). We consider two underlying fragments of SPARQL, with and without arithmetic comparisons, and we show how they affect the complexity of the above problems, and which types of data they suit most. We then study practical aspects of computing the MSSQ. In particular, we establish an important uniqueness result for MSSQs and propose an efficient approximation algorithm. We implement an algorithm for computing acyclic similarity queries and evaluate its performance on large-scale KGs; our empirical results demonstrate the practical feasibility of our algorithm.</p> |
| first_indexed | 2024-03-06T21:05:52Z |
| format | Thesis |
| id | oxford-uuid:3c6dce6e-04a1-4aee-85d9-ad45ee374fc2 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:44:07Z |
| publishDate | 2019 |
| record_format | dspace |
| spelling | oxford-uuid:3c6dce6e-04a1-4aee-85d9-ad45ee374fc22024-12-07T15:27:22ZEntity comparison in knowledge graphsThesishttp://purl.org/coar/resource_type/c_db06uuid:3c6dce6e-04a1-4aee-85d9-ad45ee374fc2Computational complexityQuery languages (Computer science)SPARQL (Computer program language)Semantic WebGraph databasesEnglishHyrax Deposit2019Petrova, AHorrocks, ICuenca Grau, BKostylev, E<p>Knowledge graphs (KGs) represent information in a simple, interlinked format and are used in a variety of applications. Besides the standard reasoning tasks such as query answering, there has been an increasing need for new types of analysis. One such fundamental analysis task is entity comparison, i.e., determining what two entities have in common and how they are different. The importance of such a task can be seen in various applications such as product comparisons, and explainable recommender systems. This thesis studies the problem of entity comparison over knowledge graphs and presents a novel framework that models comparisons via similarity and difference queries. It is the first declarative comparison framework for linked data that treats both similarities and differences as first-class citizens.</p> <p>We first define the syntax and semantics of various types of comparison queries, motivating each type with examples and establishing important relations between different query types. Next, we study the complexity of the two fundamental decision problems over queries, namely the existence and verification problems, for basic comparison queries and for most specific similarity queries (MSSQs). We consider two underlying fragments of SPARQL, with and without arithmetic comparisons, and we show how they affect the complexity of the above problems, and which types of data they suit most. We then study practical aspects of computing the MSSQ. In particular, we establish an important uniqueness result for MSSQs and propose an efficient approximation algorithm. We implement an algorithm for computing acyclic similarity queries and evaluate its performance on large-scale KGs; our empirical results demonstrate the practical feasibility of our algorithm.</p> |
| spellingShingle | Computational complexity Query languages (Computer science) SPARQL (Computer program language) Semantic Web Graph databases Petrova, A Entity comparison in knowledge graphs |
| title | Entity comparison in knowledge graphs |
| title_full | Entity comparison in knowledge graphs |
| title_fullStr | Entity comparison in knowledge graphs |
| title_full_unstemmed | Entity comparison in knowledge graphs |
| title_short | Entity comparison in knowledge graphs |
| title_sort | entity comparison in knowledge graphs |
| topic | Computational complexity Query languages (Computer science) SPARQL (Computer program language) Semantic Web Graph databases |
| work_keys_str_mv | AT petrovaa entitycomparisoninknowledgegraphs |