The Web of Data is growing in popularity and dimension, and named entity exploitation is gaining importance in many research elds. In this paper, we explore the use of entities that can be extracted from a query log to enhance query recommendation. In particular, we extend a state-of-the-art recommendation algorithm to take into account the semantic information associated with submitted queries. Our novel method generates highly related and diversi ed suggestions that we assess by means of a new evaluation technique. The manually annotated dataset used for performance comparisons has been made available to the research community to favor the repeatability of experiments.
Mining the past interactions of users with the search system recorded in query
logs is an e ective approach to produce relevant query suggestions. This is based
on the assumption that information searched by past users can be of interest
to others. The typical interaction of a user with a Web search engine consists
in translating her information need in a textual query made of few terms. We
believe that the \Web of Data" can be pro tably exploited to make this process
more user-friendly and alleviate possible vocabulary mismatch problems.
We adopt the Search Shortcuts (SS) model proposed in [
A virtual document is constructed by merging successful session, i.e., ending with a clicked query. We annotate virtual documents to extract relevant named entities. Common annotation approaches on query logs consider a single query and try to map it to an entity (if any). If a query is ambiguous, the risk is to always map it to the most popular entity. On the other hand, in case of ambiguity, we can select the entity with the highest likelihood of representing the semantic context of a query.
We de ne Semantic Search Shortcuts (S3) the query recommender system exploiting this additional knowledge. Please note that S3 provides a list of related entities, di erently from traditional query recommenders as SS that for a given query produce a at list of recommendations. We assert that entities can potentially deliver to users much more information than raw queries.
In order to compute the entities to be suggested, given an input query q, we rst retrieve the top-k most relevant virtual documents by processing the query over the SS inverted index built as described above. The result set Rq contains the top-k relevant virtual documents along with the entities associated with them. Given an entity e in the result set, we de ne two measures: score(e; VD) = (conf (e) 0 score(VD); if e 2 VD:entities
otherwise score(e; q) =
VD2Rq where conf (e) is the con dence of the annotator in mapping the entity e in the virtual document VD, while score(VD) represents the similarity score returned by the information retrieval system. We rank the entities appearing in Rq using their score w.r.t. the query. 2
Experimental Evaluation
We used a large query log coming from the Europeana portal1, containing a
sample of users' interactions covering two years (from August 27, 2010 to January,
17, 2012). We preprocessed the entire query log to remove noise (e.g., queries
submitted by software robots, mispells, di erent encodings, etc). Finally, we
obtained 139,562 successful sessions. An extensive characterization of the query
log can be found in [
We are interested in evaluating two aspects of the set of suggestions provided. These are our main research questions: 1 We acknowledge the Europeana Foundation for providing us the query logs used in our experimentation. http://www.europeana.eu/portal/ 2 Interested readers can download the dataset from: http://hpc.isti.cnr.it/ ˜ceccarelli/doku.php/sss.
Relatedness : How much information related to the original query a set of suggestions is able to provide? Diversity : How many di erent aspects of the original query a set of suggestions is able to cover?
To evaluate these aspects, we borrow from the annotators the concept of
semantic relatedness between two entities proposed by Milne and Witten [
Ps2Sq rel(Es n Eq; Eq) jSqj where Es represents the set of entities mapped to a suggestion s (could contain more than one entity in the manual annotated dataset). Please note that we remove the entities of the original query from each set of suggestions as we are not interested in suggesting something that do not add useful content w.r.t. the starting query (Es n Eq).
De nition 2 The average diversity of a list of suggestions is de ned as: div(Sq) =
jSqj
For each suggestion, we intend to evaluate how much information it adds w.r.t the other suggestions. ESqns denotes the union of the entities belonging to all the suggestions except the current suggestion s.
Experimental Results: For each set of queries in the dataset described above (short, medium and long ), we compared the average relatedness and the average diversity of the recommendations generated by SS and by S3.
Figure 1 shows the average relatedness computed for each query q belonging to a particular set of queries. Results con rm the validity of our intuition as, for all the three sets, the results obtained by S3 are always better than the results obtained by considering the SS suggestions. It is worth to observe that the longer the queries the more di cult the suggestion of related queries. This 0:3 0:15 0:32 0:31 small 0:25 0:19 medium
long 0:8 0:6 0:4 0:62 0:33 small 0:63 0:38 medium
Fig. 2: Per-set average diversity computed between the list of suggestions and the given query. 0:59 long happens because long queries occur less frequently in the log and then we have less information to generate the suggestions. If we consider single sets, the highest gain of S3 in terms of average relatedness is obtained for medium and long queries: this means that relying on entities allows to mitigate the sparsity of user data.
Figure 2 reports the average diversity of the suggestions over the queries of each set. Here, we observe an opposite trend, due to the fact that the longer the queries, the more terms/entities they contain, and the more di erent the suggestions are. Furthermore, we observe that, for the most frequent queries, SS has a very low performance w.r.t. S3. This happens because for frequent queries SS tends to retrieve popular reformulations of the original query, thus not diversifying the returned suggestions. S3 does not su er for this problem since it works with entities thus diversifying naturally the list of suggestions. We leave as future work the study of a strategy for suggesting entities aiming at maximizing the diversity on a list of suggestions.