Entity linking and resolution is a fundamental database problem with applications in data integration, data cleansing, information retrieval, knowledge fusion, and knowledge-base population. It is the task of accurately identifying multiple, difering, and possibly contradicting representations of the same real-world entity in data. In this work, we propose an entity linking and resolution system capable of linking entities across diferent databases and mentionedentities extracted from text data. Our entity linking/resolution solution, called Certus, uses a graph model to represent the profiles of entities. The graph model is versatile, thus, it is capable of handling multiple values for an attribute or a relationship, as well as the provenance descriptions of the values. Provenance descriptions of a value provide the settings of the value, such as validity periods, sources, security requirements, etc. This paper presents the architecture for the entity linking system, the logical, physical, and indexing models used in the system, and the general linking process. Furthermore, we demonstrate the performance of update operations of the physical storage models when the system is implemented in two state-of-the-art database management systems, HBase and Postgres.
In entity linking and resolution, entities refer to real-world objects (e.g., people, locations, vehicles, etc.) and real-world happenings (e.g., events, meetings, interactions, etc.). Entities are described by data in information systems. However, the descriptions may be repeated and diferent in these systems. In a database, for instance, a person may have more than one record in a table, and the records may have repeating, difering and contradicting information about the person. Likewise, two diferent databases may capture diferent information about the same entity. For example, a medical database only concerns with a person’s health related properties, whereas ∗Corresponding author. an immigration database only concerns with the truthfulness of a person’s identity.
A description of an entity is called a profile , and it can be a record in a relational database or a paragraph of words about an entity in a document. An entity may have multiple profiles in one or more sources. In other words, multiple profiles in one or more databases (or documents) may refer to the same real-world entity.
Once the profiles of entities are captured into a database, the
proifles and the entities become separated in that the users of the
database know the profiles, but possibly, not the entities. This separation
raises a serious issue. Answering the question of whether a given
profile refers to a particular real-world entity is non-trivial and
challenging. For example, given the profile: {name: Michael Jordan,
nationality: American, occupation: athlete}, there are at
least four real-world persons whose profiles in Wikipedia match
this description (see [
The goal of entity linking research is to design methods to derive an answer to the dual question: do a pair of given profiles refer to the same entity? When a pair of profiles are found to refer to the same entity, one of two actions may be taken. One is to remove of one of the profiles. This is called deduplication. The other is to merge the two profiles and this is called resolution/linking1.
Three complications make the linking/deduplication task more dificult. The first complication is from non-alignment of attributes and relationships. That is, diferent profiles describe entities using diferent attributes and/or relations. This is illustrated by the proifles p1 and p2 in Table 1. The two profiles have diferent attributes except for the name attribute. The non-aligned attributes make their match less possible. The second complication is from the multiplicity of values. For example, compared with the profile p1, the profile p3 has two name values. The third complication is the presence of provenance data. Provenance data describes the background information of a value as well as the validity period(s), security & access restriction(s), source(s), etc., of a value. For example, in p4, {since 2005} specifies when the name ‘George’ started being used, and {2010} indicates when the height valued ‘160’ was taken. Unlike non-alignment, multiplicity and provenance of values can be useful as they provide more information. However, their usefulness comes 1We consider linking and resolution, and use the terms interchangeably in this work at a cost: they require more powerful matching algorithms and data structures to enable efective usage.
This paper presents the system supporting our entity linking
method Certus [
Entity linking and resolution is a well-known database problem
that has attracted volumes of research in the literature, especially in
the relational data setting. Readers are referred to [
For accurate entity linking and deduplication, early works on the
subject examined many methods such as cosine similarity match,
distance-based match, TF/IDF, and Soundex. The well known
similarity measures for entity linking are summarized and reviewed
in [
The eficiency problem has also drawn significant research
attention. The complexity of calculating the exact similarity between
2https://www.elastic.co/
profile pairs is O(n2). Given a large number of entity profiles, say
n = 100 million, the time for computing similarity is too long to be
practical. Thus, several ideas have been introduced in the literature
to address the problem, like canopy (sorting and moving window),
hierarchical, bucketing (clustering), and indexing approaches. In
practice, the indexing approach has been found to be more useful,
resulting in the proposal of a plethora of indexing methods in the
literature (see [
In the recent years, there has been an increasing research
interest in linking entity-mentions in texts to existing entities in
knowledge-bases. From Wiki Miner in [
Most data management and software companies claim to
support entity linking in structured data, but the systems are often
not available for evaluation. In contrast, a number of open source
research frameworks are available on entity linking in text data.
For example, [
There exists works in the literature on the support and use of
provenance for entity linking. For example, [
This section covers the architecture of our entity linking system, and outlines the functions of the components of the system.
Figure 1 presents an overview of the architecture of our system. Central in the system is the Knowledge-Base (KB) which is a graph of entity profiles (details in Section 4). The profiles in the KB come from three sources: (a) ingested profiles from diferent data sources (through the Ingester) with no restriction on model; (b) extracted profiles from user-supplied textual documents (via the Text Parser); and (c) profiles created from the User-Interface (UI). The profiles are linked and indexed by the Entity Linking & Resolution (ELR) and Indexer components respectively. And, all user interactions with the system are via the UI, mediated by the Query Processor.
The following are brief details and functions of the components.
User-Interface The Ingester: maps entity descriptions from various data sources into graph-modelled profiles in the knowledge-base. Its operation is straight-forward and dependent on the respective models (or lack thereof) of the various sources of data.
The Text Parser: reads textual user-inputs (e.g., documents,
reports, etc.), and extracts mentioned-entities and their relationships
from the texts, and stores the extracted entity profiles into the
knowledge-base. In our implementation, we use Stanford NER [
The problem with the above-mentioned packages is that they may produce many triples (subject, relation, object) that do not reflect the original intention of authors in the writings. For example, extractions for the sentence “John said that, Peter has taken away the mobile phone”, include the triple: (“Peter”, “has taken away”, “the mobile phone”). This extract is only syntactically correct. The semantic correctness of this extraction is, however, dependent on John’s credibility/position. If John is a Police spokesman, for instance, then the chance of semantic-correctness would be high. However, if John is an adversary of Peter, for example, then the chance for the extraction to be correct would be low.
Therefore, we developed some heuristic rules to filter ambiguous extractions. The rules: (a) replace coreferences (pronouns) with the actual entity-mentions; (b) remove extractions that are conditional, and indirect speech; and (c) filter extractions that describes feelings and emotions. The inputs to the rule-based filtering system (RbFS) are the text and labelling from Stanford NLP. The rules improve the F1-score of extractions by 18% on average on our test datasets. The details of the RbFS is out of the scope of this paper. The Query Processor: receives requests from the user-interface and responds based on the request type. An insert or update request is directly sent to the knowledge-base. For a query by profile identifier or keywords, the index is searched and then answers are retrieved from the knowledge-base.
The Indexer: keeps the indexes up to date with the current system state. Whenever the knowledge-base is updated, this component sends the update to the indexes. The indexes support users’ queries and the ELR component. We use Elasticsearch, an open source distributed search and index engine, as our index management system. Later on (in subsection 4.3), we present details of the structure of the indexes in our system.
The ELR component: as the name suggests, is the main component in the system. In principle, for every entity profile p in the knowledge-base, indexes are read for candidate matching profiles; calculations of the similarity of p to each of the candidates are performed; and the knowledge-base is updated to store the similarities. A candidate p′ of p from the indexes is a profile that is roughly similar to p, i.e., the pair share some similar attribute and/or relationship values. We remark that the fact that p and p′ share a similar ‘word’ does not necessarily mean that they refer to the same real-world entity. For instance, if p is a male with the name Pete and p′ is a female and has a friend called Peter, then p′ can be a candidate of p as they share a similar value (i.e., Pete & Peter), but they do not match. Therefore, the indexes merely give a set of possible prolfies that may match which require further evaluation. 4
In this section, we present the logical, physical, and indexing models used in our entity linking system. 4.1
A real-world entity, naturally, has many attributes (or properties) and relates to other entities in multiple ways. An entity profile (simply, profile) captures some of the attributes and relationships of an entity; and another profile may capture diferent attributes and relationships of the same entity with possible overlaps and contradictions. For example, a person may have multiple profiles in the same/diferent sources of data (e.g., databases, knowledge-bases, social networking sites, etc.).
Entity profile structure. The data structure of profiles should be able to capture multiple values of the same attribute or relationship as well as their provenance information. This is because of the ever-changing or evolving nature of the properties and relationships of real-world entities. For example, a person may change his/her names, live at diferent addresses over time, have multiple marriages spanning diferent periods, etc. These changes lead to multiple values for attributes and relations and these values may be associated with provenance information.
We represented an entity profile as a triple p = ⟨ id, A, R ⟩, where: id is the identifier of the profile, A = [a1, · · · , an ] is a list of attribute-objects, R = [r1, · · · , rm ] is a list of relationship-objects; and each a ∈ A, r ∈ R is a set of ordered3 key-value pairs. Four profile examples are given in Table 2, shown in our structure. Profile p1 describes a person entity: a male called Peter up to 1991 and now called John. He lived_at location L1 from 1989 to 1995, owns L1 since 1989 and has a friend named Bob. Our data structure for profiles is thus able to capture the multiplicity and provenance of values.
Entity profiles graph. We use a graph model for modelling proifles, as it is capable of representing any number of attributes and relationships. Moreover, since A and R are defined as lists, instead of dictionaries, value multiplicity can be presented easily. Furthermore, the edges of the profiles graph allow the traversal of the profiles.
Formally, we use the following definition of an entity profiles graph, G = (V , E, F A ), where: (i) V is a finite set of nodes; (ii) E is a ifnite set of edges, given by E ⊆ V × V ; (iii) each node v ∈ V (resp. 3attribute/relation key-value pairs are first in the set, followed by the provenance data (if exists) p3 ⟨ L1, A = [{type: location}, {numb: 1}, {street: Brown Blvd.}, {post:2000}],
R = [{owned_by: P1, from: 1989}] ⟩ p4 ⟨ L2, A = [{type: location}, {numb: 69}, {street: Brown Ave.}, {post:5000}] ⟩ person p1 P1 friend p2 P2 person
lives_at friend from: 1989 to: 1995 lives_at from: 1990
to: 2001 lives_at from: 2001 owned_by from: 1989 owns
Legend L1 p3 location Relation-edge
Similarity-edge L2 location
sim score: 0.5 cfm: false edge e ∈ E) has a label L(v) (resp. L(e)); and (iv) each node v ∈ V has an associated list F A (v) = [a1, · · · , an ] of attribute-objects.
A node in an entity profiles graph represents a profile p, identified by the profile id, and is associated with A and R as defined. Two types of edges exist in the graph. One is called a relation-edge, derived from R. That is, the edge (rel, P1, P2) is an edge in the graph if.: P2 is the value for relation rel in P1 where P1 and P2 are profile/node identifiers. The second type of edge is called a similarity-edge, derived from the profile pair similarity and has the form (sim, P1, P2, score, c f m) where sim is a fixed label, score is the similarity score (defined later in Section 5), and c f m is a binary indicator showing whether the link-state of a profile pair has been confirmed by a user. The indicator is necessary because, in sensitive systems like policing, we want 100% precision if two profiles are linked. Thus, c f m requires user-interaction (to be discussed further in Section 5). Figure 2 is an example of the graph of profiles in Table 2. Note that each node in the graph carries its attribute list (not shown in the diagram). 4.2
Profiles are modelled as a graph; and the nodes and relation-edges are stored in one structure while the similarity-edges are stored in a separate structure. Similarity-edges are updated frequently as any profile change triggers a re-computation of similarities for the profile and other afected profiles. Therefore, storing similarityedges in a separate structure improves the update eficiency. The two structures for storing the graph are called the physical model and shown in Figure 3.
The model in Figure 3 is self-explainable; and the data in the two tables of the model are derived from some of the exemplar profiles in Table 2. The table in Figure 3(a) stores the nodes (profile ids and attributes) and relation-edges (relationships). Each node uses multiple lines and each line is for an attribute or relationship value pair with provenance details. The table in Figure 3(b), on the other hand, is for the storage of similarity-edges and each pair of profiles has an entry in the structure. simsc and rejsc represent similarity score and rejecting score respectively (details in Section 5). Since the size of the table in Figure 3(b) is the square of the number of nodes/profiles, to reduce the size, a threshold may be used to filter out very lowly-scored entries.
We realize that the performance of accessing the similarity-edge table plays a crucial role in the overall linking time performance due to its frequent update operations. Therefore, we show empirical results on three diferent implementation options of the physical model in Section 6.
Our aim is to design index structures to support users’ search for profiles and support the candidate matching-profiles generation (a.k.a blocking) of the ELR component. Thus, we use Elasticsearch, a distributed index management system that can support multiple indexes with various structures.
Recall that, logically, each profile is a triple of the form ⟨ id, A, R ⟩
in the knowledge-base. We consider two options for building
indexes for the profiles (discussed below), and both are configured
with the double-metaphone phonetic analyzer [
Keyword search & blocking indexes. The indexes that support keyword search of profiles and blocking for entity linking uses a set of words generated from the profiles. The set of words are values from the profile without provenance. That is, the provenance values, the structure, the attribute and relation names are all ignored, relationship targets (i.e., other profile ids) are replaced by the summary of the target, and all duplicate words are removed. For example, the target summary for p1 in Table 2, is a bag of the following values: “John, Peter, m, 1, brown, 2000”.
The ‘loose’ structure of these indexes guarantee high recall of search and blocking results.
Structured search indexes. The indexes for structural search consider the structure of the profiles. For example, if a user wants to find a person with “name : John, lives_at : 1 Brown street − {until : 2000}”, the index should enable p1 in Table 2 to be found. To support such structural search, we build indexes with the nested mappings in Elasticsearch for profiles structured as JSON objects with: A = [{A1 : v1, from : t0, to : t1}, {A1 : v2, to : t2}, {A2 : v3}, · · · ], where t0, t1, t2 are date time values; R mapping similarly defined.
We remark that the usage of nested mappings is critical to the preservation of the correct semantics of the multiplicity of values and their associated provenance information in Elasticsearch. Otherwise, Elasticsearch indexes the profiles in a ‘flat-format’ of the form: {A1 : [v1, v2], A2 : [v3], from : [t0], to : [t1, t2]} – which loses semantics and leads to errors and very low precision.
In settings where smaller and more precise blocking are required, the nested-mapped indexes should be used. 5
This section presents a description of our profiles comparison and linking processes. First, we highlight some relevant preprocessing steps. Then, we detail the profile-pair comparison and evaluation; and finally, give a brief overview of the match prediction and conifrmation.
Preprocesses. Prior to the calculation of the similarity between profile pairs, some preprocessing are necessary. For example, consider person and location entities: it is important to tackle the disparate representation of the same names and addresses respectively. The name Richard is often aliased as Dick; and the street-type Boulevard is often shortened as BLVD. To enable Dick to match Richard, a dictionary of name aliases of people is created (similarly, for addresses). Each name/address in a profile is checked against the dictionary. If the name has an alias, the name is expanded in the form “name alias”, e.g., “Richard Dick”. Similar operations are performed on the initials, and pre-/post-fixes of names. Similarity evaluation. Given two profiles p1 and p2, our entity linking method uses two scoring and one decision processes to determine whether they refer to the same entity in the real-world. The two scores are the similarity score, simsc, and the rejection score, rejsc; while the decision process is a data-dependency-based prediction model. We discuss the scoring here.
Given a profile p, we use the notation X ∈ p to represent either an attribute X in p[A] or a relation X in p[R]. The similarity score, simsc, of two profiles p1, p2, is calculated as follows:
Õ simsc(p1, p2) =
M(p1.X , p2.X ) · IX (p1.X , p2.X ),
X ∈p1,p2 where M is a function that returns a value indicating the level of approximate match between a pair of values for the same attribute/relation X , and I returns the level of information supplied by the match M for the values of X .
The function M considers many factors, dependent on the attribute/relation; and the values of an attribute/relation are in the form of a bag of words after synonym/alias expansion with provenance data. For example, to evaluate a name match for person entities, M considers the initials, ordering, post-/prefixes, aliases, and phonetics of names, as well as n-gram matching of character/word sequences. Edit distance is used after n-gram matching to improve accuracy and eficiency. If two values match within a user-specified threshold, then the provenance information are considered.
The function I returns the highest information level of matching values. For example, for the name-pair “John Smith White” and “Jones Smiths Green”, the Iname -weight is derived as: max { in f (John) +2 in f (Jones) , in f (Smith) +2in f (Smiths) }. The function in f (w) indicates the probability of two profiles to be linked if they match on the value w. Note that, in this example, the name-pair “Green” and “White” are not considered in the evaluation of I as they are dissimilar (i.e., have low M value). Intuitively, if a word w is rare, it has high in f (w)-value. Consider the two firstnames ‘John’ and ‘Cherith’. When two profiles share the name ‘Cherith’, the probability for the two profiles to be linked is much higher than when two profiles share the name ‘John’.
The in f (w)-value of a word w is controlled by two factors: the number m(w) of profiles sharing the word, and the number k(w) of real-world entities shared by the profiles sharing the word. If k(w) is large, the fact that the m(w) profiles share the same word contributes very little to the linking, and in f (w) should be small. When the total number of profiles increases, the chance for two profiles to share the same word becomes larger but the crucial control of the probability is still by k/m. That is, in f (w) ∝ m/k; and m can be easily obtained from word statistics but k is often unknown. A large m does not mean a large m/k ratio. We use a variation of the Sigmoid function to estimate in f (w), given as: 1 1 + exp(α · m(w) − β ) where α , β control the steepness of the decay curve and its midpoint respectively. For a given w, k(w) can be empirically estimated and linked to β . However, in general, our empirical results suggest α = 0.1 and β = 60 are suitable settings for our applications.
The rejsc score, on the other hand, is based on a simple penalty system. Given two profiles with a high overall simsc score, a penalty of 1 is added to their rejsc score if the pair are dissimilar on a key in f (w) = attribute/relation (determined by application and domain). For example, in a law enforcement context, one such key attribute for person and location entities is birth-date and zip-code respectively.
Match prediction & confirmation. As mentioned earlier, we use
a data-dependency aided decision model to predict whether a given
pair of similar profiles refer to the same real-world entity. This
decision model is a major topic (and we refer interested readers to
the paper on it in [
In some applications, even accurate prediction of the linked status of two profiles require human confirmations. Thus, our entity linking system supports this scenario, allowing the keeping of domain experts in the loop. Indeed, every similarity-edge between profiles carry the data structure for the confirmation of predicted matches (when needed). For example, in Figure 2, the similarityedge between nodes L1 and L2 is not confirmed (i.e., cfm: false). 6
In this section, we empirically evaluate the performance of the
three diferent implementations of the physical model. We remark
that, the accuracy of the ELR system is already evaluated in [
We note that updating the pairwise similarities of profiles is a major performance bottleneck. This is because, for every 1,000 profiles, the updated similarity entries are around 20,000-100,000. Therefore, we examine the time eficiency of accessing the similarity structure (Figure 3(b)).
All procedures in the work are implemented in Java, and the entity linking system runs on Ubuntu 18.04 machine(s). For singlemachine tests, the experiments were run on an Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz computer with 32GB of memory. In the cases where multi-node HBase clusters are required, an Intel(R) Core(TM) i7 CPU @ 2.30GHz computer with 16GB of memory is added. The versions of Postgres and HBase used are 9.6.12 and 1.4.8 respectively.
We present our experiment results on the eficiency of accessing the similarity structure on diferent platforms with diferent implementations. We tested the implementation in Postgres4 and HBase, with schemas summarized in Figure 5.
The operations to access the similarity structure include search, insertion, update and deletion. Since the similarity is for a pair, the search must be supported from either ID. We created two indexes for this purpose in the relational option of Postgres. With the HBase options, CF means a column family which is a dictionary of keyvalue pairs with the keys listed in the brackets. The ‘id-pair’ is constructed by ID1+"-"+ID2. In the case of HTable3 in Figure 5(c), the second id-pair is ID2+"-"+ID1.
Performance of the physical model on small to large data. In this experiment, we examine the relative update transaction (involving search, insert & delete operations) time performance of the three physical model implementations (in Figure 5) over small to large datasets. The results for: (a) small- to medium-sized data (i.e., 23K to 23M profile pairs), and (b) medium- to large-sized data (i.e., 23M to 468M profile pairs) are presented in Figure 4 (a) & (b) respectively. The x -axes show the number of profile pairs updated; and the y-axes give the average time, in seconds (on a log2 scale), taken to perform update transactions (over five iterations).
For case (a) above, the HBase-1 and HBase-2 implementations are on a single-node cluster for a fair comparison with the Postgres implementation; and for case (b), the HBase implementations are on a two-node cluster. The results show that in all cases, of the three implementation options, the relational option (Postgres) is significantly slower than the HBase counterparts; and the HBase-1 4It is noteworthy that the performance diference of the Postgres implementation for ON/OFF AUTOCOMMIT settings is marginal. Thus, we report the best (i.e., AUTOCOMMIT OFF). implementation (i.e., option (b) in Figure 5) is the better of the two HBase options. It is also noteworthy that there is no significant performance diference between the HBase implementations on single-node and two-node clusters.
Stress test of HBase implementations. In this experiment, we perform further tests to examine the insertion and update (replacement) operations of the best-performing models (i.e., the two HBase models). We consider three data sizes: 6, 30, and 54 billion profile pairs. As the results in Figure 4(c) show, the insertion operations are, as expected, more eficient than update operations for both models over the three datasets. Moreover, both the insertion and update operations are scalable for both implementations on very small-sized (i.e., just a two-node) cluster. 7
In this paper, we present the details of the entity linking system that powers our entity linking method called Certus. We describe the architecture of the system, the graph and data models, and index structures used to support the multiplicity and provenance of attribute and relation values, for efective entity linking and resolution. Further, we give the details of the physical model for storing the entity profiles graph, and discuss three diferent implementations of the structure for storing the similarity-edges. Due to the frequency of the update transaction of similarity-edges, we perform experiments to evaluate the time performance of accessing the similarity structure on two state-of-the-art database management systems (HBase and Postgres) to demonstrate the relative performances of the three diferent implementations. The empirical results show a generally good performance for all implementation options. In particular, the HBase implementation options, with even just one- or two-node clusters, scale very well for huge data sizes.
This work is supported by Data to Decisions CRC, ILE/ELR Project DC160031, funded by the Australian Commonwealth Government’s CRC Programme. And, partly supported by Data61 - CSIRO. Intl. workshop on Exploiting semantic annotations in information retrieval (ESAIR) (2013).