The generation of entity identi ers is a key issue in the context of semantic web technologies. Entity identi ers are needed when we perform any kind of operation (e.g., reference, match, disambiguation) on entities. In this paper, we present a methodology for generating entity identi ers which can be well integrated in the Entity Name System of the OKKAM infrastructure: a system for managing entity identi ers. Our approach is based on a known labelling scheme for directed acyclic graphs. Unlike other related approaches, it allows to keep track of the lineage of an entity over the operations of creation, merge of entities, and split of a single entity. This feature is important in a identi er generation framework because it can allow both local deprecation detection between two entities, as well as the reconstruction of the origin of an entity partially described in di erent sources (i.e., knowing which entity attributes are coming from which sources).
The main goal of the OKKAM project is to enable the Web of Entities. This
will be accomplished by supporting the use of globally unique identi ers for
entities with the aim that the same object will always be referred by the same
identi er. It is important to clarify that the goal of OKKAM is not to create
a comprehensive knowledge base of information about entities (i.e., attributes
of an entity and their values, like for example name:John surname:Doe), but,
instead, to create a collection of entity identi ers. The subpart of the entire
OKKAM infrastructure that has the role of managing entity identi ers is the
Entity Name System (ENS), presented in [
Within this architecture, the current way for generating IDs is the process
described in [
We now describe by way of an example the possible operations that can be
applied to an entity. A knowledge-based system, at some point in time, might
have a wrong representation of an entity: for example, initially, a system has
the knowledge that a person is called John Doe, but, after having acquired
more evidence, the system knows that another person, named John J. Doe, is,
actually, the same entity. In this case the two entity representations as well as
their EIDs need to be merged. Also, the entity itself can change over time (e.g.
semantic evolution, evolution of documents [
Merge When two entities are matched, and recognized to be the same, they are merged, and the same has to be done to their EIDs. For example, John Doe and John J. Doe are two di erent entities which are then mapped to the same person. 1.2
The reason why we include lineage information directly in the EIDs is mainly for e ciency reason. Using EIDs for lineage preservation we can easily reconstruct ancestors and descendants2 of EIDs locally, without having to query a remote ENS service provided by OKKAM. For example, when a mail is received by someone, an exchange of data and metadata happens. The mail can contain 1 http://www.okkam.org/ 2 According to split/merge operations, see Fig. 1. named entities that OKKAM tools will recognize and associate an EID to each of them. Also, when some already existing EIDs arrive from the sender they need to be matched with the local (i.e., receiver's) EID repository. At this point, some EIDs will be recognized and relevant local metadata can be shown to the user. Some other EIDs will not be recognized because they are not yet present in the local machine. At this point, using classical EIDs, the local system should query an OKKAM node in order to resolve the entities which are unknown. Using lineage preserving EIDs an intermediate step can be performed before querying the remote system. It is possible, for example, to check whether the incoming EIDs are obsolete versions of entities known by the local system. It is also possible to check if the local EIDs are obsolete versions of the incoming EIDs thus updating the local knowledge. These operation are possible just by using the EIDs without querying a remote system. The advantage is that, when the OKKAM infrastructure will be widely used, a lot of system load on the ENS can be avoided by redistributing some of it on the clients.
Another desired aspect is the possibility to decide whether two EIDs which are related by an ancestor/descendant relationship are actually the results of a split or merge operation. For example, in Fig. 1 we can see the lineage of an entity representation A which has been rst created, then merged with another entity B after a mapping operation, and, nally, split into two di erent entities D and E after obtaining more knowledge (i.e., semantic annotations) on it. If the local system already knows A and it receives the EID C, then knowing that this is the result of a merge operation, it can safely replace all the occurrences of A with C. In the other case, if the local system already knows C and it receives the EID D, it is not able to decide autonomously if it should be replaced by D or by F, but only that C is deprecated and that the system should query a remote OKKAM node for updating it.
From the described scenario we can now extract a list operations that the EIDs generation algorithms should support. We have seen that it is important to be able to: { create EIDs for unknown entities; { resolve whether a given EID A is an ancestor of an EID B; { deciding whether two related EIDs are the result of a split or of a merge operation; { retrieve the list of all the ancestors of an EID; { retrieve the list of all the descendants of an EID.
As we will present in Section 3, using EIDs for lineage preservation, some of these operations can be handled locally, without the need to query a remote system, and others still require a remote query can be optimized selecting only some candidates thus reducing the number of requests to be sent at the remote node.
Our solution to entity identi cation aims at assigning a label to each node in the lineage graph (see Fig. 1), that is, assigning an identi er to an entity, so that its lineage of creation, splits, and merges, is stored in its EID. We can easily see that the generated graph is directed and acyclic. Therefore, we can adapt a known algorithm for labelling Directed Acyclic Graphs (DAGs) to our purpose, as presented in the next section. Our approach, based on DAGs labelling, is formally de ned in Section 2. In Section 3, we critically discuss the advantages and the disadvantages of our approach, and, in Section 4, we conclude the paper. 2
In this section we describe the entire framework of entity identi cation we propose in detail. First, we describe an algorithm for labelling DAGs, the adaptation of this algorithm to the context of entity identi cation, and, then, how DNS can be used for linking EIDs with user-friendly names. 2.1
Wu et al.[
Prime number factorisation. PLSD is based on the well-known fundamental theorem of arithmetic (or unique prime factorisation theorem), from number theory, which states that any natural number greater than 1 can be written as unique product of prime numbers. The idea of PLSD is then to assign a unique prime number EID to each vertex in the DAG, and label each vertex with the product of its ancestors' prime number EIDs. Thus, given a vertex label, by performing a prime number decomposition, we can retrieve the EIDs of all its ancestors. More formally this gives: De nition 1. Let G = (V; E) be a DAG, with V a set of vertex and E a set of edges. We de ne the bijective function p : V ! N such that p(v) is prime, for v 2 V .
De nition 2. Let G = (V; E) be a DAG. We de ne the label of a vertex v 2 V as L(v) = (c[v]) where c[v] = p(v) with parents(v) being the set of vertex parents of v0.
Now, given a vertex v and its label c[v], the fundamental theorem of arithmetic assures that there exists a unique prime factorisation of c[v] such that c[v] = p(v)
Y
v02ancestors(v)
p(v0)mv0
(1)
(2)
where ancestors(v) is the set of all the ancestors of v, for some mv0 2 N; which
gives us v's ancestors' EIDs. An example is shown in Fig. 2.
Optimisation. As we can see in Fig. 2, the ancestor labels c[v] are growing
exponentially due to the mv0 's from Equation 2 which are in general greater than
1. This requires a storage space such that it is not much more space-e cient than
simply storing the ancestors' EIDs as a list for each vertex. To avoid this, Wu
et al.[
8 lcm (c[v10]; : : : ; c[vn0]) c[v] = p(v) < : 1 if in degree(v) > 0 and v10; : : : ; v20 2 parents(v) if in degree(v) = 0 (3) where lcm(a1; a2; :::; an) is the least common multiple of the natural numbers a1; a2; :::; an, with the special de nition of lcm(a) = a. Fig. 3 shows how the DAG depicted in Fig. 2 is labelled using ancestor labels as de ned in Equation 3.
Wu et al. also present a topological sort before labelling a DAG, and de ne
a PLSD-Full labelling scheme for the computation of a vertex's parents, but
we omit their description here since they are not useful or applicable in our
situation. The version we presented about is referred to as PLSD-Lite. See their
paper[
Considering the entity EIDs evolution as a DAG, we can use the PLSD labelling scheme described in Section 2.1 to locally detect if an EID has been deprecated. As in Fig. 4(a), if an EID A is deprecated by another EID B, then there exists a directed edge A ! B. As a consequence the merge and split operations mentioned in Section 1.1 are modelled as illustrated in Fig. 4(b) and 4(c) respectively.
(a) (b) (c)
We annotate each node of the DAG such built with a pair of natural numbers: the self-label, and the ancestors-label. The self-label is a unique prime number (i.e., from all the self-labels, a self-label appears once and only once), and the ancestors-label of a vertex is the product of its self-label with the least common multiple of the ancestors-labels of its ancestors (i.e., its in-component). Formally this gives: by a pair (iself ; iancestors) with iself ; iancestors 2 N+, where De nition 3. Let G = (I; D) be a DAG with I a set of vertices representing EIDs, and D a set of edges representing deprecation. We identify a vertex i 2 I i) iself is a prime number such that there exists a bijection between I and the set Iself fjself jj 2 Ig ii) iancestors = iself lcm(as1elf ; : : : ; asnelf ) with a1; : : : ; an the ancestors (incomponent) of i We call i = (iself ; iancestors) the Lineage Preserving ID (LPID), iself the selflabel of i, and iancestors its ancestors-label.
Lemma 1 shows that, given two LPIDs as de ned in De nition 3, the fact that the self-label of one LPID divides the ancestors-label of the other LPID implies that the former is deprecated.
Lemma 1. Let i = (iself ; iancestors) and j = (jself ; jancestors) be two LPIDs. jancestors=iself 2 N implies that i is deprecated.
We can now formalize in Algorithms 1, 2 and 3 the three operations de ned in Section 1.1: create, merge and split respectively.
Require: I the set of attributed LPIDs of the form i = (iself ; iancestors) 1: create the LPID j = (l; l) with l the lowest prime such that l 2= frjr = iself ; i 2 Ig 2: add j to I 3: return j
Require: M I, with I the set of attributed LPIDs of the form i = (iself ; iancestors) 1: create the LPID j = (l; l lcm (m1; : : : ; mn)) to the lowest prime l such that l 2= frjr = iself ; i 2 Ig with fm1; : : : ; mng M 2: add j to I 3: return j Require: j 2 I, n 1 2 N, with I the set of attributed LPIDs of the form i = (iself ; iancestors) 1: create empty set S 2: for k = 1 to n do 3: create the LPID sk = (l; l iancestors) to the lowest prime l such that l 2= frjr = iself ; i 2 Ig 4: add sk to I 5: add sk to S 6: end for 7: return S
For using the proposed PLSD-Lite version presented in Section 2.1, we must make sure that the considered directed graph is actually acyclic. The acyclic nature of the graph naturally follows from Algorithm 2 line 3, and Algorithm 3 line 4 where incoming edges are added only to newly created vertices which did not belong to the set of vertices I before the respective operation is executed. This implies that, using the create, merge and split operations, a deprecatedby edge d = (i; j) can only be created if i 2 I and j 2= I, i.e. 8i 2 I no new incoming edge can ever be created. Thus, the graph G = (I; D) is acyclic. 2.3
A Domain Name System (DNS) is used on the Internet to resolved user-friendly domain names (like www.L3S.de) into IP addresses usable by hosts computers and routers for transmitting data. A DNS is a hierarchical distributed map. We propose to use it for attributing user-friendly names (domain names) to EIDs.
DNS is an application layer core service widely used in today's internet.
It is described in details in RFCs 1034 and 1035 [
At each node of the DNS tree so-called Resource Records (RRs) can be
stored. Several types of RR are described in the RFC 1035 [
The maximum number of entities which can be identi ed depends on the
the maximum length of the RDATA eld, and of the rst part of the LPID
RDATA indicating the bit length of the self label. Let us take as a reference the
number of addresses that IPv6 can handle, namely 2128. To give an idea, this
corresponds approximately to 5000 URIs per square micrometer on earth, on the
whole planet. Using the Prime Number Theorem, we can approximate the 2128th
prime number to 2128 ln 2128 3 1040 which requires log2(1040) = 135 bits
to write. We thus need the bit length of the self-label: 8 bits (and it is su cient
to can write the self-label bit length of 135), then the maximum self-label takes
135 additional bits, which makes a total of 143 bits. According to RFC1035[
RDLENGT H self label is at least b( z2}1|6{ z1}3|5{ )=135c = 483. Experiments will be performed in the future to further investigate the space requirements of the LPIDs. 3 3.1
We proposed the LPIDs for being able to determine locally if an EIDs a is an ancestor of another EID b as described in Section 1.2, i.e. to perform the operation isAncestor(a; b). For this we proposed to use prime numbers as self-label, and the product of the self-label with least common multiplier of the self-labels of the ancestors as an ancestors-label, which we described in Section 2.2. This solution has to be compared to using arbitrary IDs as self-label, and storing the the enumeration of ancestor IDs as ancestors-label. The LPID approach has the advantage of time e ciency. When creating an EID, to compute the ancestor-label the LPID solution will require the computation of the least common multiplier only of the parent's ancestors-labels; whereas the enumeration solution would require to collect the list of all ancestors of the new ID (not only of its parents) with a graph-search algorithm, and then remove duplicate EIDs, requiring in turn to rst sort the collected EIDs. Also, to perform the operation isAncestor(a; b) the LDIP approach requires a single division, whereas the list approach requires to compare a with all ancestors of b.
Regarding the space e ciency, things are less clear. On one hand, storing the product of n integers does require less space than storing their enumeration. Let us take the example of two integers 3 and 5. Storing their product requires log2(3 5) = 3:9 bits. However we cannot store 0:9 bits, so we need 4 bits to store the product. Similarly to store 3 we need dlog2(3)e = 2bits and dlog2(5)e = 3 bits. The required space to store the enumeration is already 2 + 3 = 5 bits, i.e., 1 bit more than to store the product. Additionally, given the sequence of bits 3 5 representing the enumeration, in our example z1}|1{ z1}0|1{, we also need to know where the rst integers ends (or where the second begins). For this we can add the length of bits of the rst integers, e.g., on 4 bits. This would then become 2 3 5 0z0}|10{ z1}|1{ z1}0|1{, which gives a total of 9 bits for the enumeration versus only 4 bits for the product solution.
On the other hand, if we take the enumeration approach, we do not need to limit ourselves to prime numbers for the self-labels. Thus the integers to be stored in this case are smaller than in the case of the LPID approach. We will perform an in-depth comparison of space and time e ciency of the two approaches experimentally as future work. 3.2
Our Lineage Preserving IDs de ned in Section 2.2 are not URIs as de ned by
RFC3986[
URIs[
Given that we can include the lineage into the ID of an entity, we show hereafter
how we can use it to signi cantly reduce the number of requests to the ENS in
order to insure that an entity is represented by one and only one EID in our
local entity repository. Let us consider an entity repository using EIDs issued
by the ENS. The EIDs can come from di erent sources: from the local system
itself when extracting entities and querying the ENS to obtain an EID, or also
from other systems when exchanging metadata on entities{and thus exchanging
their EIDs as well. Given an EID in our local repository, it is quite possible that
since the time it has been retrieved from the ENS, the latter deprecated it and
replaced it with one or more other EIDs, depending on whether there was a
split or a merge{or a sequence of them. The fact that an EID is deprecated is
not annoying in itself, as long as this EID represents only one entity considered
in our local repository, and this entity is represented only by this EID in the
local repository. This latter condition is equivalent to ensuring that no EID
in our repository is an ancestor EID in the same repository. We call this local
deprecation. This is exactly what the LPIDs allow, using the isAncestor(a; b)
operation. Thus, using LPIDs, we will be able to locally detect{i.e. without
querying the ENS{all suspect EIDs and query the ENS for up-to-date EIDs
only for entities represented by those. In comparison, to achieve the same sound
consistency with traditional (non lineage preserving) EIDs, we have to query for
the up-to-date EID for each and all entities in our local repository. This saves a
huge amount of communications with the ENS, and also spares a lot of workload
to the ENS.
Universally Unique IDenti ers (UUIDs) are de ned in RFC 4122 [
Name-Based A name supposed to be unique in a given name-space is hashed (either with MD5 of with SHA-1) to create the UUID. The uniqueness is then relayed to the uniqueness of the name in the name-space.
Random Uses purely or pseudo random numbers to generate UUIDs with low collision probability.
Our URIs are not UUIDs in the sense that we need a centralized authority ensuring the uniqueness of the self-labels. On the other hand URIs based on PLSD allow for local deprecation detection, which is a decisive advantage in a fast evolving environment. 4
In this paper, we presented a novel approach for identifying entities. Our approach, based on a known labelling scheme for DAGs, can be well integrated in the ENS infrastructure replacing already existing techniques for EID generation.
We now discuss the strong and weak points of the presented approach. As already said, the main novelty of this EID generation technique is the possibility of preserving the information about the history of an entity using only its ID. The possible operation that we consider are entity creation, entities merge, and entity split (i.e., creation of two di erent entities out of one). Such LPIDs allow to locally detect the deprecated IDs which require an update, as described in Section 3.4, thus allowing huge communication reduction and resource savings on the ENS. One possible drawback of our approach is the size of the generated EIDs. As discussed in Section 2.3, depending on the number of managed entities the size of the EID may vary. The number of entities to be managed is di cult to predict. Basically, in our approach, we would have one single (possibly not connected) graph of EIDs. A possible solution for this is to construct EIDs based on the entity types having di erent graphs for di erent kind of entities (e.g., EIDs for people, EIDs for scienti c publications, and so on). A deep understanding of the e ciency and scalability of the proposed approach remains as future work.
In the future we also want to investigate the possibility to build PLSD EIDs
which are also UUIDs in the sense of EIDs preserving lineage and generable
without centralised administration. We want also to investigate how we can use
locality-sensitive hashing algorithms[
Acknowledgements. We thank the anonymous reviewers for their valuable comments. Moreover, we thank Peter Fankhauser for his help in producing the nal manuscript. This work is partially supported by the FP7 EU Large-scale Integrating Project OKKAM Enabling a Web of Entities (contract no. ICT215032). For more details, visit http://fp7.okkam.org.