We see the local content from peers organized in directories (i.e., on local ordered lists) of local representations of entities from the real world (e.g., persons, locations, events). Di erent local representations can give di erent \versions" of the same real world entity and use di erent names to refer to it (e.g., George Lombardi, Lombardi G., Prof. Lombardi, Dad). Although the data from these directories are related and could complement each other, there are no links that allow peers to share and search across them. We propose a Distributed Directory System that constructs these connecting links and allows peers to: (i) maintain their data locally and (ii) nd the di erent versions of a real world entity based on any name used in the network. We evaluate the approach in networks of di erent sizes using PlanetLab and we show that the results are promising in terms of the scalability.
We see Internet as a network of peers (a P2P network) organizing their content
in directories, which digitally represent their own versions of entities that exist
in the real world. Entities can be of di erent types (e.g., person, location, event
and others), they have a name, and are described by attributes (e.g.,
latitudelongitude, size, birth date), which are di erent for di erent entity types [
In this network, the di erent directories contain related data and, to some extent, they can complement each other. One problem that prevents us from exploiting the relation between these data is that there are no links connecting the local directories from peers. An e ort to connect related data on the web is that of Linked Data1, which allowed linking important datasets like, dbpedia, Freebase, DBLP, ACM, and others. Nevertheless, this approach leaves out of 1 http://linkeddata.org/ the semantic web the individual users (i.e., simple normal peers) and the data from their local directories stored in personal devices (e.g., smart-phones, PDAs, notebooks, etc.). We propose building a distributed directory that constructs the connecting links among the local directories at this level, i.e., the level of simple peers with personal devices. It it important to note that the whole directory can be seen as another dataset, which could be included as another node in the Linked Data graph. In this way, the directory would become the bridge that allows simple peers to participate as part of the semantic web as opposed to act only as consumers of it.
As in any directory, a peer normally identi es and distinguishes an entity
from others by means of names (e.g., George Lombardi, Trento, Italy, University
of Trento), which play a di erent role from the other attributes because they are
identi ers rather than descriptions [
The approach we propose for a Distributed Directory System (DDS) incorporates the notion of a real world entity described by di erent local representations from peers. This notion is used to organize the references to the local representations in order to allow nding all the available information about entities. Our system o ers two main features: { First, it takes into consideration that multiple, possible di erent, names can be used to identify the same real world entity (e.g., George Lombardi vs. G.
Lombardi and Italy vs. Italia). { Second, it allows peers to have control over the privacy of their data because the DDS stores only the names of the entity and a link to the local representation.
As a result, any name that is used in some local representation to identify an entity can be used to nd all the di erent versions of that entity that are stored in the network of peers.
The paper is structured as follows. Section 2 presents a motivating example that shows a world of related directories, while Section 3 formalizes the basic notions that link the di erent directories. In Section 4, we explain the name matching problem that arises when linking di erent directories. Then, a distributed entity directory is proposed in Section 5 and the algorithms to perform search in such directory are explained in Section 6. The implementation and the evaluation details are discussed in Section 7. Finally, the related works are discussed in Section 8 and the conclusions are presented in Section 9. 2 http://wordnet.princeton.edu/
Nowadays, most of the organization of our data is done in terms of directories. A well known and old example is the telephone book directory, used to organize address and phone numbers of people and companies. Newer forms of directories can be seen, for example, in contact lists, document directories, event directories (i.e., calendars or agendas) used by peers in current devices (e.g., computers, PDAs, smart-phones) to organize the local representation of entities of their interest. Moreover, the data from di erent directories (possibly from di erent peers) can be related. Di erent peers attending to the same event might store local representations of the event. Each of them might also have the contact information of the other peers attending to the event, e.g., a meeting.
Prof. G. Lombardi email: george@disi.unitn.it … p1 CONTACT LISTS ENTITY DIRECTORY p2
Lemomomabibill::a g r3de4io6,r0 Gg0e.8 @76d8is6i.u nitn.it ahGmdoeodmrborieerl::sg s 3e0:44 L V66oi01am04 Sb84o7a4l6tr3ed82ri62i 1 5, Trento, TN … Giulio A. Lombardi
home: 0461915923 p3
DE URL: p1/enGty/2 Names: • Prof. G. Lombardi
DE URL: p2/enGty/1 Names: • Lombardi, G.
DE URL: p3/enGty/9 Names: • Gerorge Lombardi
Prof. G. Lombardi George Lombardi
Lombardi, G.
WE URI: uri/enGty/1 URLs: p1/enGty/2 p2/enGty/1 p3/enGty/9
Let us consider in details the example of contact lists in di erent devices from the peers of a network that connects students, researchers and professors among them (e.g., SmartCampus3), and with their family members. The rst part of Figure 1 (upper part) shows that the contact list of each device can be seen as a local directory of people. Di erent peers in this network can have di erent information about the people in their contact lists, like phone numbers, email addresses, skype user and others, which show di erent ways to get in touch with them. For example, suppose that p1 is a student that is taking a course with prof. George Lombardi and therefore p1 has, in its contact list, the university email address of the professor. A researcher p2 that is working with him could have more information, like his email and mobile phone number. On the other hand, a family member p3 may have his home address and phone number but not the university email (because such information is not relevant for p3).
Now, suppose that another researcher in the network, let us call it p4, hears about prof. Lombardi work and wants to contact him. We can see that: 3 http://www.smartcampuslab.it 1. First, the information that p4 needs is distributed in the network and the problem is knowing where the di erent pieces are stored 2. Second, the di erent peers can call the same person using di erent names, e.g., Prof. Lombardi, George Lombardi, G. Lombardi. In our example, this means that p4 need to be sure that the other peers (i.e., p1, p2 and p3) are all referring to the same person as he is. 3. Third, the contact information can change in time. The work email of Prof.
Lombardi will change if his a liation changes, his phone numbers can change at any time, and his address will change if he changes residence. 4. Finally, the privacy and the sensitiveness of the information have to be considered. Most likely the phone number and address of the home of prof. Lombardi would be more private than the university email. As a consequence, p3 will not share such information with everyone. 3
We de ne a Directory of Entities that formalizes the links between data from di erent directories through the distinction between a Digital Entity (DE) and a Real World Entity (W E). A DE is de ned as a local representation of an entity that exist in the real world. A U RL (Uniform Resource Locator) is used in order to uniquely identify a DE and it can be used (by dereferencing) to obtain the full local description (i.e., based on attributes). We also consider a set of names fN g as the human readable identi ers used in DEs to refer to a W E and distinguish it from others. Formally,
DE = hU RL; fN gi (1)
On the other hand, a W E represents the real world entity and is modeled as a class of DEs. We use a U RI (Uniform Resource Identi er) to uniquely identify each W E. Formally,
W E = hU RI; fU RLgi (2) where fU RLg is a non-empty set of identi ers of di erent DEs that describe W E. As a consequence of the composition of these de nitions we can see that multiple sets of names are given to a W E through DE de nitions from di erent peers that describe the same W E.
In the second part of Figure 1 (lower part) we show how the example from Section 2 can be formalized in terms of these notions (i.e., DEs and W Es). We can see a one-to-one mapping between the W E from an entity directory and the real person represented in di erent contact lists. Moreover, we see that an entry from a contact list is translated into a DE in the directory (i.e., also a one-toone mapping). There is a one-to-many relation between W Es and DEs which shows that each single entry in a contact list correspond to one person but one person can be described in many di erent entries (possibly from di erent peers). Finally, the relation between N ames and W Es introduces a name matching problem that is better discussed in the following section.
Note that these notions allow the separation between \what" is being represented and \where" is being represented. This separation is needed in order to model the issues stated in items 1 and 2 from the example of Section 2. The DEs model the di erent pieces of information that p4 needs and their U RLs tell us where they are. The W E models the link that connects di erent DEs and its U RI identify what they represented. Regarding item 2, we can see that di erent sets of names are given in DEs, which models the fact that p1, p2 and p3 can de ne the di erent names that they use to call an entity.
On the other hand, the distinction between the two notions (DE and W E)
also provide the infrastructure to deal with the issues introduced by the other two
items (i.e., items 3 and 4 in Section 2). The dynamism of the information about
the entities and the privacy of local data are constrained to a ect DEs. In this
way, when the email of Prof. Lombardi changes (see Figure 1), p2 (the researcher)
updates its local representation (i.e., the DE). The corresponding W E de nition
is not a ected by this update, nevertheless the information (available in the P2P
network) about Prof. George Lombardi is updated. Similarly, access control can
be implemented over the data associated to each single DE representation, which
do not a ect W E de nitions. Note that such implementation (i.e., access control
implementation) is out of the scope of this paper, but the interested readers are
invited to see (for example) [
Names are human readable identi ers that serve the purpose of distinguish an
entity from others. They are labels composed by a combination of words,
numbers and symbols [
The name variations together with the DE de nition presented above, show
that the relation between names and DEs is of the type many-to-many. In
turn, this leads to a name-matching problem when we intend to search an entity
based on its names [
In this paper we propose a Distributed Directory System (DDS) that organizes information about entities incorporating the notions of W E and DE, which were presented in Section 3. These notions allow the separation of the problem of nding the DEs that represent di erent versions of a W E from the problem of nding W Es that are identi ed with multiple names. We exploit this separation by building two di erent indexes, one to deal with each problem.
A DEindex is created to map W Es (i.e., U RIs) to DEs (i.e., U RLs) and can be formally de ned as,
DEindex = fW E ! DE j6 9W E0 ! DE 2 DEindex s:t:; W E0 6= W Eg (3) We can see that this index encodes the one-to-many relation between W Es and DEs because the mapping of di erent W Es to the same DE is not allowed. On the other hand, a WEindex is created to map the names that are given (in local representations) to W Es (i.e., U RIs). Let us call fN DEg to the set of names of a digital entity DE. Then, the WEindex can be formally de ned as, W Eindex = fN ! W E j 9W E ! DE 2 DEindex s:t:; N 2 fN DEgg (4) We can see that this index encodes the many-to-many relation between N ames and W Es because the only constraint on the mappings is related to the existence of a local representation that gives \support" to such mapping.
Let us now discuss in more details how the publication, maintenance and search of entities are done in the DDS :
The publication and deletion of DEs in the network are the two main events that modify the DDS by a ecting the content of the indexes de ned above. The publication of a DE a ects both indexes in a straightforward manner. First, the DE is associated to the W E that it represents by adding the corresponding mapping (i.e., W E ! DE) to the DEindex. Second, the mappings NiDE ! W E, of each name NiDE in fN DEg to the W E that is associated to the DE, are added to the W Eindex. In order to do this, we assume that the peer locally caches the identi er (i.e., the U RI) of the W E that is represented by its DE4. On the other hand, when a DE is deleted from the network, only the DEindex is directly a ected. The same mapping W E ! DE that is added when the DE is published, is then removed from the DEindex when the peer deletes the DE. Regarding the W Eindex, we say that it is not directly a ected because the mappings of names can be removed only after verifying that they are no longer valid to identify the corresponding W E. Such veri cation is further discussed as part of the DDS maintenance.
The maintenance of the DDS is performed through periodic checks over the
indexes in order to detect and remove entries that are no longer valid. In the
DEindex, an entry can be considered invalid if it contains mapping to a DE
that has been unreachable for a long time. In order to detect this situation, each
entry is attached with a timestamp corresponding to the last time when the
DE was reachable. This timestamp is updated in every periodic check. When
the DE is not reachable, the interval between the last reachable time and the
current time is veri ed. The corresponding entry is removed from the DEindex
if such interval exceeds a given threshold. An entry from the W Eindex, on the
4 Note that the initial identi cation of the W E described by a DE is a problem of
identity management and is out of the scope of this work. See for example [
Search in the DDS can be performed using two di erent types of identi ers, U RIs and names. In this context, having as input a U RI means that the target W E has been uniquely and fully identi ed. Therefore, the goal of the search is to obtain all the di erent representations (i.e., the DEs) of the W E. On the other hand, in a search based on names, we need to nd the candidates W Es (to be the right answer) as a consequence of the many-to-many relation between names and W Es. After the candidates W Es has been found, we can use the search by U RI to nd the di erent representations of them. In what follows, the search by names is considered in more details while the search by U RIs is included as a part of the former.
A query is formally de ned as Q = fN Qg; where fN Qg is the non-empty set of names used to identify one target W E. Then, the problem of searching entities based on their names can be seen as retrieving W Es that are described in the network by at least one DE, such that, the intersection between fN DEg and fN Qg is not empty. This de nition considers a partial matching between fN DEg and fN Qg in order to allow nding a W E from any of the names given to it on di erent DEs. In turn, this can be translated in the formal de nition of the Query Answer (QA) as follows:
QA = fhW E; fDEgi j 9N 0 2 fN Qg : N 0!W E 2 W Eindex ^ 8DE0 2 fDEg : W E ! DE0 2 DEindexg (5) As we mentioned before, this answer is build in two steps. The algorithms that perform the two steps are presented in Section 6. 6
We assume that the indexes o er non-blocking APIs (to allow the parallelization of index lookups), which mean that a call to the GET function on the indexes returns immediately a reference to an object that will be lled with the results from the index lookup. In Algorithm 1, we de ne the global data structures, which are strictly related to the indexes. They are used across the di erent functions involved in the search. We use the statement for all (line 6 in Algorithm 2 and line 8 in Algorithm 3) to denote the concurrent execution of the statements that are in its body (i.e., line 7 in Algorithm 2 and lines 9 to 24 in Algorithm 3).
The Search Entity function is presented in Algorithm 2 and is the main entry point for the search by names. This function receives the query names and returns a set of candidate W Es according to the constraints given in Equation 5. In order to measure how relevant each candidate W E is, we count the number of query names that match with the names associated to the W E. This relevance is associated to each candidate W E and included in the resultset. In line 7, the rst step of the search by names is initiated with the call to the GetW Eindex function of the W Eindex. The object returned by the function is given to the corresponding handler function, which knows how to process it. Algorithm 1 Global Data Structures 1: WEAnswer : hisComplete, name, weAnsValuesi 2: DEAnswer : hisComplete, URI, deAnsValuesi 3: isComplete : boolean . TRUE when the index lookup is nished 4: weAnsValues : NULL OR fURIg OR fURLg OR ffURIg [ fURLgg 5: deAnsValues : fURLg . not empty set of URLs Algorithm 2 Search Entity 1: function SearchEntity(names : fnameg) ! fhWE, relevanceig 2: WEs : fhWE, relevanceig . stores search results 3: WE : hURI, fURLgi . fURLg.size == 1 when URI == NULL 4: relevance : integer 5: WEs := fg 6: for all name 2 names do . Parallel threads 7: HandleWEAnswer(GetWEindex(name), WEs) 8: end for 9: return WEs 10: end function
The Algorithm 3 shows the HandleW EAnswer function, which is in charge of processing the values retrieved from the W Eindex. We can see from lines 4 to 6 the loop that waits until the answer is completed. Then, in line 8, we start one execution thread to process each retrieved value. A value returned from the W Eindex represents a W E, it can be a U RI or a U RL (see line 4 from Algorithm 1). In the former case, we say that the W E identity is known. The corresponding instance is created (line 10 in Algorithm 3) with the global identi er and an (up to now) empty set of DEs. In the later case, the U RL identi es a W E with no global identi er and we assume that there is only one DE that describes it (line 18 in Algorithm 3).
In lines 11 and 19, we check whether the W E is already in the result-set. If it is, we call the function relevanceWE++, which increments the count of the relevance that is associated with the W E. Otherwise, we add the W E to the result-set with a relevance count initiated to 1 (lines 14 and 22). At this point, if we are in the case of a W E with global identi er (i.e., with a U RI), the second step of the search is initiated with the call to the GetDEindex function of the DEindex (see line 15). The object returned by the function is given to the HandleDEAnswer function, which then process it.
Algorithm 3 Handler of the WE Answers 1: function HandleWEAnswer(weAnswer : WEAnswer, WEs : fhWE, relevanceig) 2: waitingTime : integer 3: waitingTime := 5 . parameterizable waiting time 4: while weAnswer.isComplete = FALSE do 5: WAITms(waitingTime) . speci ed in milliseconds 6: end while 7: if weAnswer.weAnsValues 6= NULL then 8: for all weAnsValue 2 weAnswer.weAnsValues do . Parallel threads 9: if isURI(weAnsValue) then 10: wEntity := hweAnsValue,fgi 11: if wEntity 2 WEs then 12: relevanceWE++(WEs, wEntity) 13: else 14: add(WEs,hwEntity,1i) 15: HandleDEAnswer(GetDEindex (weAnsValue), WEs) 16: end if 17: else 18: wEntity := hNULL,fweAnsValuegi 19: if wEntity 2 WEs then 20: relevanceWE++(WEs, wEntity) 21: else 22: add(WEs, hwEntity,1i) 23: end if 24: end if 25: end for 26: end if 27: end function Algorithm 4 Handler of the DE Answers 1: function HandleDEAnswer(deAnswer : DEAnswer, WEs : fhWE, relevanceig) 2: waitingTime : integer 3: waitingTime := 5 4: while deAnswer.isComplete = FALSE do 5: WAITms(waitingTime) 6: end while 7: addDE2WE(WEs, deAnswer.key, deAnswer.deAnsValues) 8: end function
Finally, the Algorithm 4 shows how the values retrieved from the DEindex are handled. First, we wait until the answer is completed (see the loop from line 4 to line 6) and then the values are used to update the resultset. Note that the function addDE2WE takes the key (i.e., the U RI) to identify, in the resultset, the W E that has to be updated. The values (i.e., the U RLs) are then associated to such W E in order to complete the QA. We say that this function (called in line 7 in Algorithm 4) adds DEs to a given W E from a given set.
We implement the distributed directory on top of a P2P network, where the distribution of the indexes is done using a Distributed Hash Table (DHT). DHTs5 allow the peers participating in the network to store and retrieve pairs of key and value. In particular, we use TomP2P6, an advanced DHT library that extends the basic functions of DHTs. The library supports storing multiple values mapped to the same key and distinguishes between di erent index domains. The execution of the operations over di erent index domains can be seen as having di erent DHTs, i.e., one for the DEindex and other for the W Eindex.
We are interested in the evaluation of the approach under realistic network conditions and we want to measure how much the performance decreases when the size of the network grows (i.e., the scalability). The performance is considered here in terms of the time that takes the system to process a query. We use PlanetLab7 as a testbed because we believe it gives us the realistic network conditions that we need. PlanetLab provides a network of computers (i.e., nodes) that are distributed around the world, connect to each other through the internet and are available for research purposes. We perform the evaluations on networks of 50, 100 and 150 peers and the data extracted from the proceedings of the International Joint Conference on Arti cial Intelligence (IJCAI)8 are used to generate the data-sets. We use the titles of publications, names of authors and names of locations related to the conference.
Each data-set is produced by generating triples of hN ame; U RI; U RLi. The names and U RIs are replicated in order to simulate di erent W Es having the same name and di erent peers storing DEs that describe the same W E. Let us call pn to the popularity of a name n (i.e., number of W Es that are called by n) and pwe to the popularity of a W E (i.e., number of DEs that represent W E). First, for each name n, we generate pn triples with the same name (di erent U RI and U RL). Second, for each U RI, we generate pwe triples with the same name and U RI but with di erent U RLs. The popularities pn and pwe follow a Zipf9 distribution, which means that there is a long tail of unpopular names and W Es. The distribution of both popularities are independent, which means 5 http://en.wikipedia.org/wiki/Distributed_hash_table 6 http://www.tomp2p.net/ 7 https://www.planet-lab.eu/ 8 http://ijcai.org/ 9 http://en.wikipedia.org/wiki/Zipf's_law that a popular W E do not necessarily has a popular name and vice versa. We assume that the local entity base of each peer contains, in average, 2000 DEs. We have overall around 100000, 200000 and 300000 DEs. The query set for each peer is generated by randomly selecting a set of 1400 names from the initial set of entity names.
During the evaluation, we rst index the data-set for the corresponding network size and then the peers begin the search evaluation process pseudosimultaneously. In this process, each peer performs the following steps: (i) takes a query from the query set, (ii) runs the search, (iii) measures and logs the time that the system takes to respond to the query, (iv) waits a random interval of time (between 1 and 3 seconds), and (v) go back to step (i). These steps are repeated until the end of the set of queries. Once all the peers end the search process, we compute the average query time for the network. We show the results for the di erent network sizes in Table 1. The values for the average query times are stable with the network growth and we believe this is a promising result regarding the scalability of the directory. On the other hand, when comparing to information retrieval systems (in general), the average times for search are still high.
In order to have better understanding of the query times that contribute to these averages, we analyze the distribution of the query time in the di erent networks. In Figure 2 we show the results of this analysis, where we can see that also the query time distribution is stable with regard to the network growth. Also in Figure 2 we can notice that more than 55% of the queries are actually answered in less than a second, while in almost 70% of the cases the response arrives in less than 2 seconds (which is less than the average time). Moreover, only 9% of queries take more than 5 seconds to be answered.
Fig. 2. Query time of di erent networks
It has to be noted that the results are returned after the query answer is
complete, i.e., once all the lookups involved in the query have ended. This means that
100%
80%
60%
40%
20%
0%
a single slow lookup is enough to delay the computation of a query answer and
therefore increase the query time. Furthermore, we know that particularly slow
peers can produce this problem when a lookup has to be routed through them.
We believe that, in the big picture, the scalability of the approach is a promising
and important result. On the other hand, there are some techniques to perform
result catching or to avoid routing through slow peers (see for example [
The work introduced in this paper involve the approaches that are capable of managing information about entities in a P2P network. More speci cally, our approach deals with the distributed indexing and searching of entities based on their identi ers. To the best of our knowledge there are no approaches that integrates these areas, i.e., that performs search of entities over a p2p network. Nevertheless, we give an overview of related approaches from both areas.
Some entity aware approaches concentrate the attention on the de nition
of models and structures for the representation of entities [
Other approaches that perform search following an entity centric perspective
can be found in the literature [10{12]. Entity search engines are proposed in [
On the other hand, we have P2P approaches, which perform distributed
search but are not aware of entities [
We can nd also more structured approaches that aim to guarantee the
location of the content shared on the network (e.g., CAN [
We presented and approach for a distributed directory of entities that introduces the notions of DE and W E in order to link local directories of di erent peers. The directory provides search services based on entity identi ers. In particular, we presented the algorithms for searching entities based on their names. We discussed the name matching problem that appears as a consequence of the many-to-many relation between names and W Es. Then, we showed that, by its design, our directory deals with the problem of matching names inside the network (i.e., the rst part of the name matching problem).
The data from peers are stored locally, only the identi ers and the links to the local representations are indexed. This infrastructure allows the implementation of access control mechanisms on the local representations in order to deal with privacy issues. At the same time, the changes made by peers in local representations, are available in the directory in a straightforward manner. The indexes are distributed using a Distributed Hash Table (DHT) but the directory de nition is independent from a speci c underlying DHT implementation.
The evaluation of the search was performed on networks of 50, 100, and 150 peers running on PlanetLab. The average query time (as a measure of the performance) for di erent network sizes were presented as well as the distribution of the query times. The results can be considered promising in terms of scalability because the performance is stable with the network growth.
As part of the future works, we want to study and integrate (possibly existing) approaches to deal with the problem of matching queries with the names used in the network (i.e., the second part of the naming problem). Additionally, we want to better understand the di erent elements that in uence the search performance in order to nd and implement techniques to reduce the query times. 10 http://en.wikipedia.org/wiki/Gnutella