License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2015.25
URN: urn:nbn:de:0030-drops-49759
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4975/
Burdick, Douglas ;
Fagin, Ronald ;
Kolaitis, Phokion G. ;
Popa, Lucian ;
Tan, Wang-Chiew
A Declarative Framework for Linking Entities
Abstract
The aim of this paper is to introduce and develop a truly declarative framework for entity linking and, in particular, for entity resolution. As in some earlier approaches, our framework is based on the systematic use of constraints. However, the constraints we adopt are link-to-source constraints, unlike in earlier approaches where source-to-link constraints were used to dictate how to generate links. Our approach makes it possible to focus entirely on the intended properties of the outcome of entity linking, thus separating the constraints from any procedure of how to achieve that outcome. The core language consists of link-to-source constraints that specify the desired properties of a link relation in terms of source relations and built-in predicates such as similarity measures. A key feature of the link-to-source constraints is that they employ disjunction, which enables the declarative listing of all the reasons as to why two entities should be linked. We also consider extensions of the core language that capture collective entity resolution, by allowing inter-dependence between links.
We identify a class of "good" solutions for entity linking specifications, which we call maximum-value solutions and which capture the strength of a link by counting the reasons that justify it. We study natural algorithmic problems associated with these solutions, including the problem of enumerating the "good" solutions, and the problem of finding the certain links, which are the links that appear in every "good" solution. We show that these problems are tractable for the core language, but may become intractable once we allow inter-dependence between link relations. We also make some surprising connections between our declarative framework, which is deterministic, and probabilistic approaches such as ones based on Markov Logic Networks.
BibTeX - Entry
@InProceedings{burdick_et_al:LIPIcs:2015:4975,
author = {Douglas Burdick and Ronald Fagin and Phokion G. Kolaitis and Lucian Popa and Wang-Chiew Tan},
title = {{A Declarative Framework for Linking Entities}},
booktitle = {18th International Conference on Database Theory (ICDT 2015)},
pages = {25--43},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-79-8},
ISSN = {1868-8969},
year = {2015},
volume = {31},
editor = {Marcelo Arenas and Mart{\'i}n Ugarte},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4975},
URN = {urn:nbn:de:0030-drops-49759},
doi = {10.4230/LIPIcs.ICDT.2015.25},
annote = {Keywords: entity linking, entity resolution, constraints, certain links}
}
|
Keywords: |
|
entity linking, entity resolution, constraints, certain links |
|
Collection: |
|
18th International Conference on Database Theory (ICDT 2015) |
|
Issue Date: |
|
2015 |
|
Date of publication: |
|
19.03.2015 |
