This paper describes the analysis we performed for the query success task of LogCLEF 2011. In particular, we address the issue of query re nement. The motivating assumption of our work is that query success can be improved by a system that can make good query re nement suggestions. We investigate how log les as provided in LogCLEF can assist in learning good suggestions. We used the distributed search logs of Deutscher Bildungsserver (DBS) and the logs of The European Library (TEL). We rst processed the logs to extract the actually submitted search queries together with user session information and the browsing information following the submission of a query. Our initial analysis shows that a large proportion of the sessions on DBS in particular resulted in reformulations of the original query. The focus of our work is to demonstrate that the given log les can be used to acquire structured knowledge that can assist users in searching the collections (and thus shortening the number of steps needed when compared to a system that does not employ query modi cation suggestions). We use the paradigm of ant colony optimisation to derive query suggestions and evaluate the results by applying the fully automated AutoEval methodology that relies entirely on the search logs.
LogCLEF provides a platform for researchers to conduct analysis on the search logs of live search engines to understand user search behaviour and study the exploitation of search logs as implicit source of feedback. LogCLEF provides a standard evaluation resource which makes systems comparable and makes research more transparent, in particular because large search engines do exploit their search logs but do not grant public access to them.
This year LogCLEF tries to tackle three di erent tasks, (a) language
identi cation, (b) query classi cation and (c) query success. In this paper we study
a sub-task of the third task which is query re nement. We perform an analysis
on two di erent datasets provided for LogCLEF 2011, namely the DBS and the
TEL datasets. We then apply Ant Colony Optimisation as an adaptive learning
approach to build knowledge structures from the query re nements in the logs.
These knowledge structures can be exploited to aid users in nding what they
are looking for and hence accelerate the success of user searches. We evaluate
these structures with the AutoEval evaluation methodology which relies entirely
on the logs and does not involve users [
In this section we described the datasets used in the experiments and present the initial analysis of the datasets. We also highlight the main initial ndings and the di erences in those datasets. 2.1
The German Web site Deutscher Bildungsserver is a clearing house for educational resources on the Web. The logs distributed for the LogCLEF task are general logs in a standard format and cover a period of three months from September to November 2009. These logs record all user interactions with the Web site including queries that have been submitted to their search engine and the results that have been viewed upon issuing the queries. Each record in the log represents a request to the server that contains the user session information together with a timestamp of the request, the destination and source URLs and browser information. We processed the logs to extract the queries submitted to their search engine together with the user session information and the browsing information upon submitting the query. These steps were followed to process the logs: 1. Discard all records that are not search-related. Search-related records have the elds `metasuche' or 'qsuche' in the URLs. 2. Discard all records that are requests from search engine bots (Google, MSN,
Yahoo!). 3. Order records by their session ID and their timestamp. 4. Extract the queries and the actions following each query in each session. The queries are passed in the `feldinhalt`' parameter of the URL. 5. Case-fold all queries and URL-decode the queries as they are a parameter in the URL.
To illustrate how this is done, let us consider the entries of the logs in Figure 1. All these entries represent HTTP requests to the server and are within one user session identi ed by the rst string hash. They can also be ordered by their timestamp. The rst two entries (1) and (2) are discarded as they are not related to search. The third entry is a search request where the query can be extracted from the URL parameters `schulp icht'. The fourth entry represents a request that follows the search but is discarded as it is a browser request to a script le. The fth entry is another search request with a query 'schulp ichtiger Kinder'. Entry (6) is a click request on the results displayed for the query `schulp ichtiger Kinder', whereas the last entry (7) is a further browsing step after viewing the result. the proportion of the sessions which contain more than one query is around a quarter with an overall average session length of 1.50 queries.
More than half of the queries were not followed by any user clicks on the results. The average number of clicks is quite low 0.69.
The number of distinct queries within those are 31,347. Table 2 lists the top queries submitted to the search engine with their frequencies. Not surprisingly they are all in the German language.
Query Frequency Query Frequency quereinstieg 2505 englisch 208 suchbegri 1387 praktika 205 quereinsteiger 689 vorbereitungsdienst 198 stellenangebote 435 deutsch 182 lehrplan 407 bildungsplan 180 lehrplane 303 praktikum 179 abitur 293 grundschule 159 seiteneinstieg 283 adhs 148 mathematik 224 geschichte 138 referendariat 223 seiteneinsteiger 138 We have used log data that have been collected on the search engine of the European Library (TEL)1. The TEL logs contain an entry for every user interaction with the TEL portal. Log entries contain the type of action performed (e.g. simple or advanced search, changing system options) and attributes such as user ID, session ID, the interface language, query, and timestamp. Figure 2 lists some sample entries, the rst one describing a search for \pomegranate fertilization" submitted through the simple user interface.
The logs record not just all queries submitted to the search engine but also other activities such as viewing a result. TEL logs have already been used in LogCLEF 2009 and 20102. This year a new log le was distributed and covers the period from 1 January 2010 till 30 December 2010. That is the le we used.
In the logs there is a great inclination towards using simple search compared
to using advanced search [
We have used TEL logs in the past [
With this processing we extracted 162,642 queries that have `English' as the
query language in 75,100 unique sessions from the total 806,155 interactions in
the le. Figure 3 presents two sample entries in the processed query logs (using
the 2008 logs and reproduced from [
In Table 3 we compare both logs DBS and TEL 2010. The DBS search engine has more tra c and the average session length in the DBS logs is shorter.
Table 4 lists the most frequent queries in TEL 2010. By comparing this to the most frequent queries in DBS we can observe that the TEL query logs are more sparse. The frequency of the top queries in TEL 2010 are much less than the top ones in DBS. We have recently explored the application of Ant Colony Optimisation (ACO) to build query association graphs from the query logs for the purpose of query
Query Frequency Query Frequency
ditt legeme er ditt 308 maps 96
mozart 287 dante 95
art 189 bach 91
text 155 see 90
napoleon 148 water analysis 88
a 147 shakespeare 86
music 120 harry potter 84
meer dan een baan 115 michalopoulos 82
digital 107 map 80
hippo et hippa 97 france 80
recommendation [
A user interaction with the search engine is treated as an individual ant's journey producing some pheromone and over time the collective journeys of all ants result in strengthening more popular paths, with higher pheromone levels, which leads to a corresponding term association graph. Less popular and seasonally incorrect paths will have lower pheromone levels by introducing some evaporation factor which reduces the weights of non-traversed edges over time.
Using this process, the association graph is being updated in a continuous learning cycle. The directed association graph can then be used for query recommendation as follows. Starting from the query node in question, we traverse the graph edges to identify and rank associated query nodes using the weights on the edges.
Figure 4 illustrates a partial association graph extracted by running ACO on the DBS logs. 4
The goal of the experiment is to answer these questions:
1. Does ACO learn useful query recommendations over time?
2. How does the performance of ACO in learning these suggestions di er in
both logs given the di erence we observed in the analysis between the two
datasets?
3. Can the query recommendations provided by ACO shorten the number of
steps needed by users to nd what they are looking for?
We conducted two sets of experiments to answer these questions.
We employed AutoEval which is an automatic evaluation framework for assessing
the performance of query suggestion systems over time based on actual query
logs.The validity of the framework has been con rmed with a user study [
The evaluation is performed on arbitrary intervals, e.g. on a daily basis. For example, let us assume that during the current day, three query modi cations have been submitted. For each query modi cation pair, the domain model is provided with the initial query and returns a ranked list of recommended query modi cations. We take the rank of the actual modi ed query (i.e., the one in the log data) in this list, as an indication of the domain model's accuracy. So for the total of three query modi cations in the current day, we can calculate the model's Mean Reciprocal Rank (M RR) score as (1=r1 + 1=r2 + 1=r3)=3, where r1 to r3 are the ranks of the actual query modi cations in the list of modi cations recommended by the model in each of the three cases. More generally, given a day d with Q query modi cation pairs, the model's Mean Reciprocal Rank score for that day M RRd is given by Equation 1 below.
Q M RRd = (X 1 )=Q i=1 ri (1)
Note that in the special case where the actual query modi cation is not included in the list of recommended modi cations then 1=r is set to zero. The above evaluation process results in a score for each logged day. So overall, the process produces a series of scores for each domain model being evaluated. These scores allow the comparison between di erent domain models. A model M1 can therefore be considered superior over a model M2 if a statistically signi cant improvement can be measured over the given period.
It is important to mention here that we do not try to identify query modi cations within a user session that are actually related. Therefore even subsequent queries that are not related are treated as a query modi cation pair. However these noisy query modi cation pairs do not a ect the evaluation methodology as this noise is common for all evaluated models.
We ran AutoEval on the DBS logs in the period of September to November 2009 with weekly batches and our ACO algorithm to derive query suggestions. However for the TEL logs, we used monthly batches and ran AutoEval for the entire period of the year 2010. Monthly batches were used to have somehow comparable tra c. 4.2
The second set of experiments looked at examining the e ect of query suggestions in reducing the number of steps required by user to achieve their search goals. Given a session of more then two queries we want to nd out whether our ACO query recommendation system can suggest the last query in the session. Here we are assuming that the last query in the session was a successful one as no more queries were issued afterwards. This assumption can be relaxed by looking at only session which ended up with a query followed by a single click on the results as this may a better indication of search success. For this experiment, using the DBS logs, we ran the ACO algorithm to learn an association graph on the rst 45 days of the log. For the next 45 days we extracted sessions with more than two queries. This resulted in 3600 sessions, out of which 1259 ended with a query followed by a landing page. For each of those pairs, we examined the suggestion list recommended by the learnt ACO model. 5
After running the evaluation framework on both datasets using the setup described in the previous sections, we plot the obtained M RR scores in Figures 5 and 6.
By examining those gures we can observe the following: 0.03 0.025 6 7 8
Weeks: 1 Sept - 30 Nov 2009
{ The ACO adaptive learning model is capable of learning useful relations
from the TEL logs and the DBS logs. In both cases, despite the spike, ACO
is achieving higher scores over time in both logs. This con rms ndings of a
previous study on TEL logs [
The results of the second sets of experiments are shown in table 5. This is suggesting that in about 7% of the cases the query recommendation system is able to suggest the last query to the users. The percentage is low but it is not surprising due to the sparsity and low tra c of the query logs which we discuss in the analysis section. However, a search engine with this recommendation system in place is better than the one that does not provide query suggestions as it is sometimes capable of assisting the user in reducing the path to their search goal by suggesting useful queries.
This research is part of the AutoAdapt research project. AutoAdapt is funded by EPSRC grants EP/F035357/1 and EP/F035705/1.