In this work we propose a comparative study of the e ects of a continuous model update on the e ectiveness of wellknown query recommendation algorithms. In their original formulation, these algorithms use static (i.e. pre-computed) models to generate recommendations. We extend these algorithms to generate suggestions using: a static model (no updates), a model updated periodically, and a model continuously updating (i.e. each time a query is submitted). We assess the results by previously proposed evaluation metrics and we show that the use of periodical and continuous updates of the model used for recommending queries provides better recommendations.
The ocean of data on the web is continuously growing in size. Due to this reason web search engines are one of today's most used online applications to nd what users need. According to Nielsen Online in October 2008 Google and Yahoo! answered more than 6 billions user searches in the US. In the latest years, web search engines have started to provide users with query recommendations to help them in re ning queries and to quickly satisfy their needs. Query recommendation techniques are based on the knowledge about the behavior of past users of the search engine recorded in query logs. Basically, the behavior of many individuals is smarter than the behavior of few intelligent people.
We propose a new class of query recommender algorithms that we name \incremental " query recommender systems. These kind of systems update the model on which recommendations are drawn without the need for rebuilding it from scratch. That is, at regular intervals the recommender system updates the model on which suggestions are computed. In particular, we study a class of incremental recommenders where the model is updated for each received query. We study the e ect on the performance (in terms of quality) of query recommender systems when varying the update interval. To do so, we propose an automatic evaluation mechanism to assess the e ectiveness of query recommendation algorithms.
In this paper we aim at showing a novel class of query recommendation algorithms whose models are periodically updated as queries are submitted by users, and a comparison of four di erent query recommenders using new metrics. Due to space constraints we present a shortened version of our ongoing work. 2.
To validate our hypothesis about the e ects of continuous
model updates on query recommender systems, we consider
two well-known query recommendation algorithms and we
de ne two new algorithms in order to continuously update
the model on which recommendations are computed. The
rst one uses association rules for generating
recommendations [
AssociationRules. Fonseca et al. uses association rules
as a basis for generating recommendations [
CoverGraph. Baeza-Yates et al. use click-through data
as a way to provide recommendations [
We argue that the use of \incremental" algorithms for
query recommendation can provide better results from two
main points of view: i) models age slowly (or do not age at
all), and ii) they provide better recommendations for bursty
topics [
We design two new recommender algorithms in order to allow the update of the models at regular time intervals. The two algorithms di er from the static versions by the way they manage and use data to build the model. To achieve the main challenges both the two algorithms implement LRU structures and use HashMaps to retrieve queries and links during the update phase. Doing so, a exible, small and easy to maintain model is obtained.
Assessing the e ectiveness of recommender systems is a though problem. The evaluation can be made through userstudies and through automatic mechanisms.
We validate our proposals by means of an automatic evaluation methodology consisting in using previously proposed metrics. Due to space constraints, we show in the following experiments results with the QueryOverlap metric.
Let S = fq1; : : : ; qng be a user session of length n. Let S1 = fq1; : : : ; qb n2 cg be the set of queries in the rst half of the session. For each qj 2 S1, let S2 = fqj+1; : : : ; qng be the n j most recently submitted queries in the session, and let Rj = fr1; : : : ; rmg be the set of query recommendations returned for the query. We de ne QueryOverlap as: QueryOverlap(qj ) =
K ri2Rj
sk2S2 1 X [ri = sk]f (k) where [ri = sk] is 1 i the i-th element of R is equal to the k-th element of S2, and 0 otherwise. f (k) is a weighting function allowing us to di erentiate the importance of each recommendation depending on the position it occupies in the second part of the session and K is a normalization factor.
The most important experiments we have conducted is to measure the bene ts of continuously updating models in query recommender systems. This test is conducted generating recommendations and assessing the e ectiveness of query suggestions on di erent time slots. Here, we brie y discuss only results for the AssociationRules algorithm.
From the plots in Figure 1 it is evident that the e ectiveness of the recommendations provided by both o ine and online models becomes constant from a certain period of time. However the incremental versions (both quantized and continuously updating) produce sensitively better recommendations. This is due to the inclusion in the model of new and \fresher" data. Furthermore, except for an initial phase where the model is warming up, the number of useful suggestions of the continuously updating versions of time 2 3 4 7 8 9 10 the algorithms is greater than the others throughout the entire observed period. The static and incrementally updating versions, indeed, produces more signi cant recommendations only in the very rst intervals of the timeline. This is, obviously, due to both the \freshness" of the static models in the starting phases and to the cold-start problem in the continuously updating algorithms.
As a consequence of that, we prove that the aging e ect
on the models [
In this work we propose a new class of query recommender algorithms that we name \incremental " query recommender systems. These kind of systems update the model on which recommendations are drawn, incrementally. In addition, we propose an automatic evaluation mechanism to assess the e ectiveness of query recommendation algorithms.
Results show that continuously updating versions of the algorithms generate an higher number of useful suggestions with respect to the others throughout the entire observed period. This is a consequence of the aging e ect on the models responsible for a ecting the quality of the recommendations provided.