Keyword search approaches over RDF graphs have proven intuitive for users. However, these approaches rely on local copies of RDF graphs. In this paper, we present an algorithm that uses RDF keyword search methodologies to nd information in the live Linked Data web rather than against local indexes. Users navigate between documents by specifying keywords that are matched against triples. Navigation is performed through a pipeline which streams results to users as soon as they are found. Keyword search is assisted through the resolution of predicate URIs. We evaluate our methodology by converting several natural language questions into lists of keywords and seed URIs. For each question we measured how quickly and how many triples appeared in the output stream of each step of the pipeline. Results show that relevant triples are streamed back to users in less than 5 seconds on average. We think that this approach can help people analyze and explore various Linked Datasets in a follow your nose fashion by simply typing keywords.
On the traditional \Web of Documents", navigation is
characterized by following links (with anchor text) between
documents. On the Web of Data (also known as Linked
Data), documents contain structured resource descriptions,
where resources are interlinked with speci c properties. This
increased granularity has opened the door to new approaches
for browsing [
However, users of these link traversal approaches need: (i) to provide a formal description of the portion of the Web they wish to traverse upfront and (ii) to know which URIs to follow at each step of the navigation (similar to writing SPARQL queries, for example, where users need to understand the structure of the data). Furthermore, users may time time hom etow n geo
y clocselobse by lmed actor hometown geo close by filmed actor often wish to explore di erent combinations of data sources and URIs to get a more complete picture; they are unlikely to know what navigational steps or what URIs are relevant until they actually encounter them.
In order to avoid the need for users to specify a complex
structured query upfront [
This paper continues with discussion of related work in Section 2. We introduce our methodology in Section 3 and provide a detailed algorithm in Section 4. In Section 5 we evaluate our approach against similar existing techniques. In Section 6 we conclude and discuss future work.
Several works propose methods for browsing and
navigating Linked Datasets. NautiLOD [
Instead our approach enables users to perform their
discoveries \on the go". In this sense it is somewhat similar
to Linked Data browsers such as Tabulator [
Versus keyword search approaches (e.g., see [
A related technique that combines both navigation and
search is Treo [
In terms of streaming results to users on-the- y, Triple
Pattern Fragments [
To navigate and search the Web of Data using our approach, users (or agents) initiate their browsing similar to the usual Web of Documents: they provide a list of starting locations (seed URIs).1 The navigation starts by resolving the seed URIs after which users are invited to introduce a keyword. The keyword is used to search for relevant content against the information retrieved. This process is illustrated in more detail in Figure 3 where we perform a navigation from seed URI http://harth.org/andreas/foaf#ah looking for relevant information using the keyword \known". URIs found using this keyword are sent to an output stream. In the upper-right corner we see this entire process happening again, using a new keyword and new seed URIs, namely the ones returned from the earlier step.
In the following sub-sections, we will explain in more detail the navigation and search aspects of our approach. 3.1
The type of navigation we use to browse the Linked Data
Web in a programmatic way is similar to other works such as
LDpath2 and NautiLOD [
known
interest explicit URIs or regular expressions, allowing for a more exible and less rigorous browsing experience. Furthermore, in other related approaches, users typically have to construct queries upfront and wait for the entire process to nish before they can act on the results. Instead we rely on returning results to users in a streaming fashion as quickly as possible, enabling the discovery of data as you go.
To enable the streaming of results, we structure the navigation process in the form of a pipeline. Each element of the pipeline is responsible for searching against the data it receives. Figure 4 gives an example. The resource Andreas Harth is fed into the rst element of the pipeline, and using the keyword \known", we look for relevant triples. These triples are then sent to an output, which becomes the input stream for the next element of the pipeline. Rather than having to wait for the process to nish at each step, we act on results as soon as they are found. Thus the second element can already start processing the resource Kjetil Kjernsmo even though the earlier step has not nished looking for triples. This enables users to continue the navigation using new keywords, even while other elements of the pipeline are still busy looking for relevant results. 3.2
To nd relevant triples at each step of the pipeline, several
methodologies can be used. For instance, work such as [
known
Harth <http : / / harth . org . . . f o a f#ah> f o a f : knows
<http : / / csarven . ca/#i> . f o a f : knows r d f s : comment "A person known by . . . " .
To enable further matches, we extend the search with content acquired by resolving the predicate URIs associated with the current resource. When matching RDF links, we are thus not only limited to matching tokens in the URI string itself, but can match labels, comments, etc. Figure 5 shows an example of how predicate resolution can enrich a search result. For the Andreas Harth resource, no triples are found using the keyword \known". However, by resolving predicate URIs we are able to nd triples within the foaf:knows predicate that match the keyword. We can therefore use triples with the foaf:knows predicate that are associated with our main resource to continue our navigation. http://csarven.ca/#i
Sarven Capadisli fa o f:interest rdfs:label foaf:interest \Sarven Capadisli"
Chess Philosophy Excerpt of the navigation showing the contents of the streams as the navigation proceeds along the keyword pipeline. Many predicate URIs will resolve to an entire ontology or vocabulary and not just to the term identi ed. For instance, the URI http://xmlns.com/foaf/0.1/knows resolves to a description of the entire FOAF vocabulary. For this reason our approach relies only on the triples where the resolved URI appears in either the subject or object position.
We will now describe our approach in more detail by presenting an algorithm and explaining its functionality using a walkthrough example. The question in Figure 3 involves accessing data from di erent sources and following speci c paths based on the people Andreas knows. To represent this question formally we de ne a seed URI from which the navigation initiates, and an ordered set of keywords we need to follow to answer our question (e.g., in the order entered interactively by the user). Each keyword is e ectively an element in the pipeline. Algorithm 1 gives an overview of the procedure for a single element of the pipeline.
The algorithm takes as input a stream which we call S, and a keyword k. By following Figure 3, once the URI http://harth.org/andreas/foaf#ah appears in the stream S (line 1), we resolve this URI and assign the triples returned to the set R (line 2). Next on line 3 we apply our search methodology against the set R using the keyword k (which is \known") and the found triples are assigned to the set F . If triples are found we extract the URIs from the found triples (line 5) and write the resulting URIs to our output stream out. For the keyword \known" no triples were found, therefore nothing is written to the output stream yet.
Next on line 8 we obtain triples that were not yet found and assign them to the set T . We proceed by resolving the predicate URIs of this set. We loop through each triple of this set on line 9, and we resolve each predicate on line 10. We then apply our search methodology against the set P using the keyword \known" with found triples assigned to the set F 0 (line 12); if F 0 is non-empty, we extract new Algorithm 1 Keyword-based navigation and search Input: input stream S and keyword k Output: output stream out of URIs found 1: upon U RI in stream S do 2: R triples from resolving U RI 3: F search for k in R and return triples 4: if F:length > 0 then 5: N f unvisited URIs of F except predicates g 6: out.write(N ) 7: end if 8: T R F 9: for each triple t 2 T do 10: P triples from resolving predicate of t 11: F 0 search for k in P and return triples 12: if F 0:length > 0 then 13: N f unvisited URIs of t except predicates g 14: out.write(N ) 15: end if 16: end for URIs from the current triple t (line 13). On line 14 we write the extracted URIs to the stream out. Thanks to predicate resolution, we now match triples with predicate foaf:knows, resulting in 2 output URIs, namely http://csarven.ca/#i and http://www.kjetil.kjernsmo.net/foaf#me.
Figure 3 continues by listening for the keyword \interest". The algorithm is re-executed with an input stream fed from the output stream of the earlier execution. We therefore obtain 2 URIs in the input stream; for each of these URIs the process is repeated. The process terminates when all processing has nished for the given keywords or the user manually terminates the session.
It is important to note that the resolution of URIs can occur in parallel. In the evaluation section we speci cally create a new thread for each request to obtain higher throughput. URIs resolved should also be cached to avoid unnecessary re-retrieval of commonly requested documents. known interest dbpedia airport runway 5:94 7:55 2:03 3 time(s) 74 s 63 e l p i r t 50 # match de nition 10
27 director based @it (a) What are the interests of the people known by
Andreas Harth? 2 keywords and 1 seed URI: http://harth.org/andreas/foaf#ah (b) What are the available de nitions for the English noun \apple"? 2 keywords and 1 seed URI:
http://babelnet.org/rdf/s00005054n 2:2 time(s) 4:3 6:8 10 18:4 (c) What are the lengths of the runways of the airports in Rome, Italy? 3 keywords and 1 seed URI: http://sws.geonames.org/3169070/ (d) Give me the locations of the movies directed by Ridley Scott, in Italian. 3 keywords and 1 seed URI: http://data.linkedmdb.org/resource/director/8472
The main characteristic of our keyword-based navigation
and search is that it allows to answer questions \as you
go" by simply typing keywords. The primary purpose of
this preliminary evaluation is to check whether our
identied method produces relevant results in an acceptable time
frame. To this end, we performed two di erent experiments:
1. First we executed a series of questions, each
represented as a set of keywords with a seed URI, using our
identi ed approach. We measured how fast and how
many relevant triples appeared in the output streams.
2. Next we compared our methodology against a similar
implementation called swget [
To run the experiments, we implemented our navigation pipeline component using an observer pattern and our search component as a multi-threaded Java process that uses the open source Apache Any233 library to resolve URIs and obtain triples. We instantiated keyword search by utilizing the dice coe cient 4 string matching algorithm which works especially well with strings of variable length. The swget comparison does not take into account our search methodology since we use explicit URIs. As HTTP requests were run in parallel in di erent threads, to avoid many simultaneous connections that may overload the servers and generate 3http://any23.apache.org/ 4http://www.catalysoft.com/articles/StrikeAMatch. html errors, we used a thread pool size of 5 (swget was also congured with this size). All results for all the experiments are the average of 5 runs. 5.2
Figures 6a, 6b, 6c and 6d show the contents of the various output streams at speci c times. Each plotted mark represents data being written to the stream.
We will analyze the results in terms of response time (reception of rst solution for every keyword) and navigation hop time (reception of rst solution between each keyword). For the question in Figure 6a, the response time is around 6 seconds for the rst keyword and 9 seconds for the second keyword. This is mainly due to the fact that we had to resolve the predicate URIs in order to nd triples matching the rst \known" keyword. The average navigation hop time is 7.7 seconds. For the question in Figure 6b, the response time is 2 seconds for the rst keyword and 2.3 seconds for the second. The navigation hop time is 2.2 seconds. For this question we see that the results are returned quicker because we did not have to resort to predicate resolution. For the questions in Figure 6c and 6d, triples relating to the rst keyword are found in 2.8 and 2.2 seconds respectively, 5.9 and 4.3 seconds for the second keyword, and 7.5 and 5.8 seconds for the third keyword. The navigation hop time is 5.4 and 4.1 seconds. For these two questions we see that, even with a greater number of keywords, the navigation hop time remains below 10 seconds.
In summary, in these results we can see that response times are all under 10 seconds. Even more important is the navigation hop time, which suggests that users can navigate across resources, and match relevant triples, in around 5 seconds on average. These results, although preliminary, show us that browsing the Web of Data using keywords is possible within the bounds of interactive time-frames, albeit a bit sluggish by modern browsing terms. Methods for improving response times are discussed in the future work section.
swget comparsion: The speed di erence between swget and our approach (indicated as kbld) is shown in Figure 7 where we see swget's response time increasing especially for results returned by following owl:sameAs links. With our approach the response times are stable without any relevant jumps. The quicker response times of our approach are mainly due to our pipeline algorithm which, instead of waiting for each step to nish, sends results along the pipeline as soon as they are found; our goal is speci cally to enable interactivity. swget was con gured to stream results, however, it still performs a breadth- rst search which means each step has to nish before the navigation can continue. 20 15 5 17:52 11:25 kbld swget
In this short paper we combined RDF keyword search methodologies with Linked Data traversal techniques. Preliminary results showed that combining these two methodologies { with pipeline-based navigation and predicate resolution search { enables clients to explore the Web of Data using keywords. Our approach of streaming results back to the user as quickly as possible shows that applications can be developed to make use of our keyword-based approach.
For future work we would like to further develop and
evaluate the techniques presented. Reasoning methods could be
used to induce and nd other relevant information.
BabelNet [
We would also like to look at the potential of using our
keyword-based approach inside an application such as
Tabulator [
Sapienza a liated authors gratefully acknowledge support from the LIDER project (№ 610782), a Coordination and Support Action funded by the European Commission under FP7. This work was also supported by the Millennium Nucleus Center for Semantic Web Research under Grant № NC120004, and Fondecyt under Grant № 11140900.