Recent work on searching the Semantic Web has yielded a wide range of approaches with respect to the style of input, the underlying search mechanisms and the manner in which results are presented. Each approach has an impact upon the quality of the information retrieved and the user's experience of the search process. This highlights the need for formalised and consistent evaluation to benchmark the coverage, applicability and usability of existing tools and provide indications of future directions for advancement of the state-of-the-art. In this paper, we describe a comprehensive evaluation methodology which addresses both the underlying performance and the subjective usability of a tool. We present the key outcomes of a recently completed international evaluation campaign which adopted this approach and thus identify a number of new requirements for semantic search tools from both the perspective of the underlying technology as well as the user experience.
the fourth employed a formal query approach which was hidden from the end user
by a graphical query interface. Recently, evaluating semantic search approaches
gained more attention both in IR { within its most established evaluation
conference TREC { [
The above evaluations are all based upon the Cran eld methodology [
The rst part of this paper describes an evaluation methodology for assessing and comparing the strengths and weaknesses of user-focussed Semantic Search approaches. We describe the dataset and questions used in the evaluation and discuss the results of the usability study. The analysis and feedback from this evaluation are described. The second part of the paper identi es a number of new requirements for search approaches based upon the outcomes of the evaluation and analysis of the current state-of-the-art. 2
In the Semantic Web community, semantic search is widely used to refer to a
number of di erent categories of systems:
{ gateways (e.g., Sindice [
The evaluation described here focuses on user-centric semantic search tools (e.g. query given as keywords or natural language or using a form or a graph) querying a repository of semantic data and returning answers extracted from them. The tools' results presentation is not limited to a speci c style (e.g., list of entity URIs or a visualisation of the results). However, the results returned must be answers rather than documents matching the given query.
Search is a user-centric activity; therefore, it is important to emphasise the users' experience. An important aspect of this is the formal gathering of feedback from the participants which should be achieved using standard questionnaires. Furthermore, the use of an additional demographics questionnaire allows more
4 http://www.sigir.org/museum/pdfs/ASLIB%20CRANFIELD%20RESEARCH% 20PROJECT-1960/pdfs/ in-depth ndings to be identi ed (e.g., if a particular type of user prefers a particular search approach). 2.1
Subjects are asked to reformulate a set of questions using a tool's interface.
Thus, it is important that the data set would be from an understandable and
well-known domain (and hence, easily understandable by non-expert users) and,
preferably, already have a set of questions and associated groundtruths. The
geographical dataset from the Mooney Natural Language Learning Data5 satis es
these requirements and has been used in a number of usability studies [
The questions [
Usability Di erent input styles (e.g., form-based, NL, etc.) can be compared
with respect to the input query language's expressiveness and usability. These
concepts are assessed by capturing feedback regarding the user experience and
the usefulness of the query language in supporting users to express their
information needs and formulate searches [
Analyses The experiment was controlled using custom-written software which allowed each experiment run to be orchestrated and timings and results to be captured. The results included the actual result set returned by a tool for a query, the time required to execute a query, the number of attempts required
by a user to obtain a satisfactory answer as well as the time required to
formulate the query. We used post-search questionnaires to collect data regarding the
user experience and satisfaction with the tool. Three di erent types of online
questionnaires were used which serve di erent purposes. The rst is the System
Usability Scale (SUS) questionnaire [
The evaluation consisted of tools from form-based, controlled-NL-based and
freeNL-based approaches. Each tool was evaluated with 10 subjects (except K-Search
[
Firstly, the subjects were presented with a short introduction to the experiment itself such as why the experiment is taking place, what is being tested, how the experiment will be executed, etc. Then the tool itself was explained to the subjects; they learnt about the type and the functionality of the tool and how to apply it's speci c query language to answer the given tasks. The users were then given sample tasks to test their understanding of the previous phases. After that, the subjects did the actual experiment: using the tool's interface to formulate each question and get the answers. Having nished all the questions, they were presented with the three questionnaires (Section 2.2). Finally, the subjects had the chance to talk about important and open questions and give more feedback and input to their satisfaction or problems with the system being tested.
Table 1 shows the results for the four tools participating in this phase. The mean number of attempts shows how many times the user had to reformulate their query in order to obtain answers with which they were satis ed (or indicated that they were con dent a suitable answer could not be found). This latter distinction between nding the appropriate answer and the user `giving up' after a number of attempts is shown by the mean answer found rate. Input time refers to the amount of time the subject spent formulating their query using the tool's interface, which acts as a core indicator of the tool's usability.
According to the ratings of SUS scores [
K-Search Form-based
NLP-Reduce PowerAqua
NL-based NL-based
(Ginseng [
This section discusses the results and feedback collected from the subjects of the usability study. Figure 1 summarises the features most liked and disliked based on their feedback. 4.1
On the one hand, Uren et al. [
Liked/Required View search domain
Auto-‐ compleEon
Build complex queries (AND,
OR,… ) Easy & fast
input Natural & familiar
language Feedback during query execuEon Merging results
Show provenance of results
Input format complexity
No support for superlaEves or comparaEves in
queries Slow response
Disliked Restricted language model
Requires knowledge
of ontologies AbstracEon of search domain No incremental
results Not suitable for casual users No storing/ reuse of query results
No sorEng, grouping, or filtering of results a very restricted language model. For instance, query formulation took longer using Ginseng (restricted natural language) than K-Search (form-based). This is further supported by user feedback in which it was reported that they would prefer typing a natural language query because it is faster than forms or graphs.
Kaufmann et al. [
However, natural language approaches su er from both syntactic as well as semantic ambiguities. This makes the overall performance of such approaches heavily dependent upon the performance of the underlying natural language processing techniques responsible for parsing and analysing the users' natural language sentences. This was shown by the feedback we received from users of one of the natural language-based tools, one of which was \the response is very dependent on the use of the correct terms in the query". This was also con rmed by that approach achieving the lowest precision. Another limitation faced by the natural language approach is the lack of knowledge of the underlying ontology terms and relations by the users due to the high abstraction of the search domain. The e ect of this is that any keywords or terms used by users are likely to be very di erent from the semantically-corresponding terms in the ontology. This in turn increases the di culty of parsing the user query and a ects the performance.
Using a restricted grammar as employed by Ginseng is an approach to limit
the impact of both of these problems. The `autocompletion' provided by the
system based on the underlying grammar attempts to bridge the domain
abstraction gap and also resembles the form-based approach in helping the user to
better understand the search space. Although it provides the user with
knowledge regarding which concepts, relations and instances are found in the search
space and hence can be used to build valid queries, it still lacks the power of
visualising the structure of the used ontology. The impact of this
`intermediate' functionality can be observed in the user feedback with a lower degree of
dissatisfaction regarding the ability to conceptualise the underlying data but
still not completely eliminated. The restricted language model also prevents
unacceptable/invalid queries in the used grammar by employing a guided input
natural language approach. However, only accepting speci c concepts and
relations { found in the grammar { limits the exibility and expressiveness of the
user queries. User coercion into following prede ned sentence structures proves
to be frustrating and too complicated [
The feedback from the questionnaires showed that using superlatives or comparatives in the user queries (e.g.: highest point, longer than) was not supported by any of the participating tools; an issue raised by 8 subjects in the answer of the SUS question \What didn't you like about the system and why?" and by others in the open feedback after the experiment. Only one provided a feature similar to this functionality: the ability to specify a range of values for numeric datatypes. A comparative such as less than 5000 could then be translated to the range 0 to 5000. However, this was deemed to be both confusing (since the user had to decide what to use as the non-speci ed bound) and, when the non-speci ed bounds were incorrect, having a negative impact on the results. 4.2
Speed of response is an important factor for users since they are used to the performance of commercial search engines (e.g., Google) in which results are returned within fractions of a second. Many users in our study were expecting similar performance from the semantic search tools. Although the average response time of three of the tools (K-Search, NLP-Reduce, Ginseng) is less than a second (44ms, 51ms, and 51ms respectively), users reported their dissatisfaction with these timings especially the ones who evaluated PowerAqua with response time of 11 seconds on average. The lack of feedback on the status of the execution process only served to increase the sense of dissatisfaction: no tool indicated the execution progress or whether a problem had occurred in the system. This lack of feedback resulted in users suspecting that something had gone wrong with the system { even if the search was still progressing{ and start a new search. Furthermore, some tools made it impossible to distinguish between an empty result set, a problem with the query formulation or a problem with the search. This not only a ected the users experience and satisfaction but also the approach's measured performance. 4.3
Semantic Search tools are di erent from Semantic Web gateways or entry points such as Watson and Sindice. The latter are not intended for casual users but for other applications or the Semantic Web community to locate Semantic Web resources such as ontologies or Semantic Web documents and are usually presented as a set of URIs. For example, Sindice shows the URIs of documents and, for every document, it additionally presents the triples contained within the document, an RDF graph of the triples, and the used ontologies. Semantic Search tools are, on the other hand, used by casual users (i.e., users who may be experts in the domain of the underlying data but may have no knowledge of semantic technologies). Such users usually have di erent requirements and expectations of what and how results should be presented to them.
In contrast to these `casual user' requirements, a number of the search tools did not present their results in a user-friendly manner and this was re ected in the feedback. Two approaches presented the full URIs together with the concepts in the ontology that were matched with the terms in the user query. Another used the instance labels to provide a natural language presentation; however, such labels (e.g., `montgomeryAl') were not necessarily suitable for direct inclusion into a natural language phrase. Indeed, the tool also displayed the ontologies used as well as the mappings that were found between the ontology and the query terms. Although potentially useful to an expert in the semantic web eld, this was not helpful to casual users.
The other commonly reported limitation of all the tools was the degree to which a query's results could be stored or reused. A number of the questions used in the evaluation had a high complexity level and needed to be split into two or more sub-queries. For instance, for the question \Which rivers in Arkansas are longer than the Allegheny river?", the users were rst querying the data for the length of the Allegheny river and then performing a second query to nd the rivers in Arkansas which are longer than the answer they got. Therefore, users often wanted to use previous results as the basis of a further query or to temporarily store the results in order to perform an intersection or union operation with the current result set. Unfortunately, this was not supported by any of the participating tools. However, this shows that users have very high expectations of the usability and functionalities o ered by a semantic search tool as this requirement is not provided even by traditional search systems (e.g., Google and Yahoo). Another means of managing the results that users requested was the ability to lter results according to some suitable criteria and checking the provenance of the results; only one tool provided the latter. Indeed, even basic manipulations such as sorting were requested { a feature of particular importance for tools which did not allow query formulations to include superlatives. 5
This section identi es a number of areas for improvement for semantic search tools from the perspective of the underlying technology and the user experience. 5.1 Usability The feedback shows that it's very helpful for users { especially those who are unfamiliar with the underlying data { to explore the search space while building their queries using view-based interfaces which expose the structure of the ontology in a graphical manner. It gives users a much better understanding of what information is available and what queries are supported by the tool. In contrast, the feedback also shows that, when creating their queries, users prefer natural language interfaces because they are quick and easy. Clearly both approaches have their advantages; however, they su er from various limitations when used separately as discussed in Sec. 4.1. Therefore, we believe that the combination of both approaches would help get the best of both worlds.
Users not familiar with the search domain can use a form-based or natural language-based interface to build their queries. Simultaneously, the tool should dynamically generate a visual representation of the user's query based upon the structure of the ontology. Indeed, the user should be able to move from one query formulation style to another { at will { with each being updated to re ect changes made in the other. This `dual' query formulation would ensure a casual user correctly formulates their intended query. Expert users, or those who nd it laborious to use the visual approach, would simply use the natural language input facility provided by the tool. An additional feature for natural language input would be an optional `auto-completion' feature which could guide the user to query completion given knowledge of the underlying ontology. Expressiveness The feedback also shows that the evaluated tools had difculties with supporting complex queries such as the ones containing logical operators (e.g, \AND"). Allowing the user to input more than one query and combining them with their chosen logical operator from a list included in the interface would reduce the impact of this limitation. The tool would merge the results according to the used operator (e.g., \intersection" for \AND"). For instance, a query such as \What are the rivers that pass through California and Arizona?" would be constructed as two subqueries: \What are the rivers that pass through California?" and \What are the rivers that pass through Arizona?" with the nal results being the intersection of both result sets.
Furthermore, the evaluated tools faced similar di culties with supporting
superlatives and comparatives in users' queries. Freya [
Several users reported dissatisfaction with the tools' response time to some of
their queries. Users appreciated the fact that the tools returned more accurate
answers than they would get from traditional search engines, however this did
not remove the e ect of the delay in response { even if it was relatively small.
Additionally, the study found that the use of feedback reduces the e ect of the
delay; users showed greater willingness to wait if they were informed that the
search is still being performed and that the delay is not due to a failure in the
system. The presentation of intermediate, or partially complete, results reduces
the perceived delay associated with the complete result set (e.g., Sig.ma [
Most of the users were frustrated by the fact that they didn't understand the results presented to them, feeling that too much technical knowledge was assumed. The evaluation shows that the tools underestimated the e ect of this on the users' experience and satisfaction.
Query answers ought to be presented to users in an accessible and attractive manner. Indeed, the tool should go a step further and augment the direct answer with associated information in order to provide a `richer' experience for the user. This approach is adopted by WolframAlpha6; for example, in response to `What is the capital of Alabama? ' WolframAlpha includes the natural language presentation of the answer as well as various population statistics, a map showing the location of the city, and other related information such as the current local time, weather and nearby cities.
An interesting requirement found by our study was the ability to store the
result set of a query to use in subsequent queries. This would allow more
complex questions to be answered which, in turn, improves the tools' performance.
QuiKey [
Result management was also identi ed as being of importance to users with
commonly requested functionality included sorting, ltering and more complex
activities such as establishing the provenance and trustworthiness of certain
results. For example, Sig.ma [
We have presented a exible and comprehensive methodology for evaluating di erent semantic search approaches; we have also highlighted a number of empirical ndings from an international semantic search evaluation campaign based upon this methodology. Finally, based upon analysis of the evaluation outcomes, we have described a number of additional requirements for current and future semantic search solutions.
In contrast to other benchmarking e orts, we emphasised the need for an
evaluation methodology which addressed both performance and usability [
Firstly, we found that an intelligent combination of natural language and view-based input styles would provide a signi cant increase in search e ectiveness and user satisfaction. Such a `dual' query formulation approach would combine the ease with which a view-based approach can be used to explore and learn the structure of the underlying data whilst still being able to exploit the e ciency and simplicity of a natural language interface.
Secondly, (and perhaps of greatest interest to users) was the need for more sophisticated results presentation and management. Results should allow a large degree of customisability (sorting, ltering, saving of intermediate results, augmenting, etc). Indeed, it would also be bene cial to provide data which is supplementary to the original query to increase `richness'. Furthermore, users expect to be able to have immediate access to provenance information.
In summary, this paper has presented a number of important ndings which are of interest both to semantic search tool developers but also designers of interactive search evaluations. Such evaluations (and the associated analyses as presented here) provide the impetus to improve search solutions and enhance the user experience.