Query auto-completion (QAC) is a common interactive feature for assisting users during query formulation. Following each query input keystroke, QAC suggests queries prefixed by the input characters; allowing the user to avoid further cognitive and physical effort if any are acceptable. To rank suggestions, QAC approaches typically aggregate past query popularity to determine the likelihood of a query being used again. Hence, QAC is usually very effective for consistently popular queries. However, as the web becomes increasingly real-time, more people are turning to search engines to find out about unpredictable emerging and ongoing events and phenomena. QAC approaches reliant on aggregating long-term historic query-logs are not sensitive to very recent real-time events, because newly popular queries will be outweighed by long-term popular queries, especially for less-specific prefix lengths (e.g. 2 or 3 characters). We explore limiting the aggregation period of past querylog evidence to increase the temporal sensitivity of QAC. We vary the query-log aggregation period between 2 and 14 days, for prefix lengths of 2 to 5 characters. Experimentation simulates a realtime environment using openly available MSN and AOL query-log datasets. Analysis indicates a linear relationship between prefix length and QAC performance when using different query-log aggregation periods. In particular, we find QAC for shorter prefix lengths is optimal when a shorter query-log aggregation period is used, and vice-versa, longer prefix lengths benefit from a longer query-log aggregation period.
For users, cognitively formulating and physically typing queries
is a time-consuming and error prone process. As such, query
autocompletion (QAC) [
As a user types their query into the search box, QAC attempts to predict the completed query the user may have in mind. Following each query input keystroke, QAC suggests possible queries (which we refer to as completion suggestions) beginning with the already input character sequence (i.e. prefix). The goal for effective QAC is to present the user’s intended query after the least possible keystrokes, and at the highest rank in the list of completion suggestions.
Conventional QAC approaches rank completion suggestions by
aggregating their popularity in past query-logs. Further work has
incorporated personal contextual features for short prefixes [
Figure 1 illustrates the ten completion suggestions offered by
Google for the three character query prefix ‘hur’ on November 8th,
2012. The list of query suggestions indicates the historically most
likely queries to be submitted with the given prefix, possibly in the
context of some undisclosed ranking features such as geo-location
or the user’s past queries. Despite the recency and prominence of
Hurricane Sandy, the query ranks very low in the completion
suggestions, while ‘hurricane isaac’ ranks first, regardless that it
occurred many months previously. Aside from this issue, QAC for
short and unspecific prefixes (i.e. 1 or 2 common characters) is
often unsuccessful as there are usually a huge number of possible
completion suggestions [
With the web increasingly becoming a platform for real-time
news and media, time plays a central role in information
interaction. A substantial volume of daily top queries are the result of
users turning to search engines for up-to-date information about
very recent or ongoing events [
As time undoubtedly plays a central role in user search behaviour
[
Relying on a long period of past query-log evidence will ensure QAC is robust for continually popular queries, however, it will also have the effect of smoothing over short-term popular queries. For example, imagine a scenario where query q1 is consistently popular, appearing 1000 times each day in the query-log. Aggregating query popularity over a past 30 day period would mean that query q2 which is popular only today would need to be appear 30,000 times before it outweighed the long-term popular query in a probabilistic QAC approach. At the same time, reducing the aggregation period may mean the long-term popular query q1 is not adequately represented, allowing short-term noise to reduce its ranking.
Ultimately, developing an effective QAC system that can respond to real-time temporal trends is a trade-off between robustness and sensitivity. In this paper we aim to study this trade-off in terms of how much past query-log evidence is optimal for aggregating query popularity, and how this changes for each prefix length. Moreover, as there has been little experimentation on open datasets, this work establishes baseline QAC performance for further studies.
The effectiveness of using a shorter query-log evidence
aggregation period has been noted previously, particularly for real-time
temporal queries [
We quantify the extent to which the query-logs are composed of real-time temporal querying, in order to determine the degree to which QAC must support this behaviour. We define real-time temporal queries as those which appear as a ‘spike’ - with the vast majority of their occurrence within a short period, e.g. hours to days. Similarly, the queries are unlikely to have been recently popular, or even seen previously.
We analyse the temporal trends contained in two publicly
available2 datasets: the AOL [
The AOL query-log contains 36.3M user interactions over a 3 2MSN available on request. We justify our use of AOL as we study the data without identifying individuals. month period from the 1st March 2006 to the 31st May 2006. The MSN query-log contains almost 14.9M user interactions over a 1 month period from the 1st May 2006 to the 31st May 2006.
Query-log entries necessary for identifying result clicks were removed. By extracting all the unique query and timestamp combinations, we obtained only queries directly typed by users. Navigational queries containing the URL substrings: .com, .net, .org, http, .edu or www were removed. We were left with 21.8M and 12.2M queries for AOL and MSN, respectively. Preliminary analysis discovered a sizeable number of short bursts of what we suspect is bot spamming activity in the AOL query-logs. Generic queries such as ‘personalfinance’, ‘aolcelebrity’, ‘computercheckup’, appear in high volume with very uniform spacing (e.g. every 30 or 60 seconds). We manually observed and removed around 10,000 instances of these queries from our analysis.
Volume of Queries Window Size (Days) 1 3 5
AOL 9.2% 10.1% 10.4%
MSN 3.5% 4.5% 5.1%
In Table 1 we present the volume of queries (i.e. % of the total queries submitted in the query-log) which occur four or more times, and have at least 80% of their use concentrated within a period of N days. In AOL, the most popular 1 to 5 day highly temporal queries include: ‘amelia earhart pictures’, ‘karl der grosse’, ‘the simpsons live action’ and ‘leisure suit larry’. Likewise, in MSN among the most popular are: ‘stephen colbert’, ‘poison milk’, ‘ohio bear attack’ and ‘kimberley dozier’. Investigation shows that many of these queries describe, or are strongly related to significant events.
These results suggest a reasonable volume of real-time temporal queries in both query-logs, at least in the relatively short periods we are able to study. We suspect that the percentage of real-time temporal queries will have substantially increased in more recent query-logs, given the increase in real-time media available on the internet. 3.
The majority of research has concentrated on the inherent engineering complexity of providing efficient and scalable QAC, which is resilient to typing errors. There have been relatively few studies on improving QAC effectiveness in search engines; likely due to the fact that there are few suitable query-logs available outside industrial search engine companies for experimentation.
Exploiting the user’s personal context, and past query sessions
has led to considerable QAC improvement, especially for shorter
prefixes [
The common “standard” approach to QAC is Maximum
Likelihood Estimation (MLE), based on past query popularity (i.e. ‘most
popular completion’) [
MLE(rn) = arg maxP(q) q2Q (1)
P(q) is the probability of the query appearing in the past querylog. We refer to this method, aggregating all query-log evidence prior to the current time qt as our baseline MLE-ALL. 4.1
We propose using only the last N days of query-log evidence (e.g., N = 2, 4,7 or 14 days) for computing P(q) at qt (i.e., a sliding window of past evidence). We refer to this approach as MLE-WN.
The intuition underlying this approach is that a more recent and limited period of queries may more accurately reflect the current query distribution. Similarly, although consistently popular queries will still be adequately reflected in the distribution, their total frequency will no longer be great enough to outweigh the frequency of popular queries that only spike in shorter periods.
The objective of our experiment is to study the trade-off between sensitivity and robustness of QAC, for different prefix lengths. As such, we explore various query-log aggregation periods for each prefix length, and measure the effect on overall QAC performance.
Our experimental methodology simulates a real-time user search scenario; such that the user types a prefix, and receives completion suggestions based only on evidence prior to the time of their query. QAC effectiveness is measured by the presence, and rank of a ground-truth match for each set of suggestions.
A time-ordered query-log provides a stream of ground-truth user queries. We assume that each query present in the query-log is the result of a user having manually typed it into the search box. As such, for each prefix of length n of the query, QAC provides completion suggestions. Each suggestion is matched with the groundtruth of the user’s actual query (we discuss matching in the following section).
Evaluation Metric. Similar to past QAC work [
RR(S; qintended ) =
1 S; Rank(qintended ) (2)
If no match for qintended is present, then a RR of 0 is assigned (avoiding divide by zero errors). MRR is then computed as the arithmetic average of RR for all queries.
MRR reflects the user interaction model of QAC; a higherranked completion suggestion is more beneficial, but the difference in ordering of lower-ranked completion candidates is less significant. That is to say, there is less noticeable difference between a correct completion suggestion ranked at either the 3rd or 4th position, compared to the 1st or 2nd position. We consider a literal lower-case string match between completion suggestion and ground-truth as a successful match.
We conduct experimentation using the AOL and MSN query-log datasets. By experimenting with millions of queries contained in each query-log, we achieve a representative indication of how each approach would perform in a real-world setting.
Using two different query-logs validates the approach across two
query samples of varying characteristics, and different user
populations of the two industrial search engines. The exact sampling and
construction of each query-log is unknown. MSN has been filtered
for privacy (e.g. clearing known number patterns, such as phone
numbers), appears to contain fewer adult queries, and is more
indepth as it is only for a one month period. In contrast, the AOL
query-log contains more queries, but has greater breadth as it
covers a three month period. However, as noted in [
We report results in Section 7 for two QAC settings: MLEALL using all query-log evidence prior to qt (we treat this as the baseline), and MLE-WN, with 2,4,7 and 14 days of past querylog (characterising short and medium-term event/evidence periods). With only sampled query-log datasets, reducing the evidence period further leads to relatively sparse querying data. To emulate a real user interface scenario, we assume the user would see 4 highest-ranking completion suggestions for each prefix they input.
We run each approach for all query prefixes of 2 to 5 characters. Experiments for each prefix length were run independently, hence a successful completion suggestion at a prefix of 2 characters had no effect on the later evaluation for 3 characters.
Learning Period. We report the MRR of MLE QAC computed over the period of the query-log, minus the first N days which we treat as the learning period. Doing this makes the MRR obtained from MLE-ALL and MLE-WN directly comparable as both are computed over exactly the same set of queries. In any case, QAC performance during this early period will be extremely low as there is very little query popularity evidence (i.e. the ‘cold-start problem’), and wouldn’t reflect a real-world scenario where a QAC system would almost always be trained on past evidence. 7.
Table 2 presents the overall MRR observed for MLE QAC experiments on the AOL and MSN and AOL query-logs; using the past 2, 4, 7, 14 days as well all past query-log evidence, for prefix lengths of 2 to 5 characters. The MLE-ALL MRR reported beside each MLE-WN corresponds to the baseline using all queries prior to qt , but with the first N days of queries excluded for comparison.
The aggregated statistical power of 21.8M and 12.2M RR
measures (i.e. each query) provided by the AOL and MSN experiments,
respectively, means that the results we report are statistically
significant according to standard t-tests [
Firstly, for all runs and both query-logs it is clear that QAC is
considerably more effective with a longer (i.e. more specific)
prefix. This is expected, given that each extra character in the prefix
reduces the space of possible completion suggestions, thus
increasing the chance of a completion suggestion match [
QAC is almost always more effective for MSN than for AOL, especially for prefix lengths of 4 or less characters. Using a sliding window of evidence has a significant effect on overall QAC performance in almost all cases.
For AOL there is a sliding window of evidence which can imr AOL MSN 0.090 0.143 0.185 0.217 0.112 0.164 0.197 0.215 prove QAC performance over MLE-ALL for all prefix lengths, albeit relatively marginally for 5 characters. Using a shorter 2 day window of evidence improves QAC performance by up to nearly 3% for shorter prefixes of 2 or 3 characters. For a prefix of 4 characters, using a little more evidence, e.g. 4 days is optimal. Similarly, the best performance for a 5 character prefix is obtained when using 14 days of evidence.
For MSN, shorter prefixes (e.g. 2 or 3 characters) can outperform the baseline when using a window of evidence. Specifically, we see the best performance improvement of nearly 4.5% when using 2 days of evidence for a 2 character prefix. However, using between 2 and 14 days of query-log evidence always impairs QAC performance compared to the baseline for 4 or 5 character prefixes. Notably, the detrimental effect on performance is reduced as the sliding window of evidence is increased.
The baseline QAC performance, and the following sliding
window QAC improvement characteristics for each query-log are
considerably different between the query-logs. AOL QAC is
marginally but consistently improved in almost all cases, whereas
MSN QAC is only improved for shorter prefixes, albeit much more
so than for AOL. This suggests that the two query-logs have
different temporal characteristics. In part, this may be caused by a
couple of factors. Firstly, although AOL has more queries, it is
spread more sparsely over a three month period, in contrast, MSN
queries are concentrated in a 1 month period. Additionally, AOL
has a day of missing data [
Although the performance improvement characteristics for each prefix and sliding window are different for each query-log, there is a clear overall linear relationship emerging in the results between prefix length and optimal sliding window period. As such, QAC for shorter prefixes performs optimally with a shorter sliding window of evidence, and conversely, QAC for longer prefixes performs best with a longer sliding window of evidence.
This relationship probably arises from the uncertainty posed by
short and non-specific prefix lengths [
Conclusion. In this paper we examined the trade-off between QAC robustness and real-time temporal sensitivity. We found that QAC effectiveness can be improved by up to nearly 5%, simply by selecting the optimal time period of query popularity aggregation for each prefix length. The period necessary to achieve optimal QAC effectiveness varies by prefix length; shorter prefixes (e.g. 23 characters) perform best with only short-term evidence (e.g. 2-7 days), whereas longer prefixes (e.g. 4-5 characters) require more long-term evidence (e.g. 7-14 days, or more). Results also indicate the need to train per query-log, in order to capture intrinsic temporal and demographic characteristics. Care must also be taken with the sampling of queries used for training.
Further work will experiment with larger, more recent querylogs and perform cross-validation to verify the preliminary findings we present in this paper. Moreover, we will investigate alternative modelling techniques to improve QAC effectiveness for real-time temporal queries, which are problematic for time-series modelling as they spike so briefly in time.
Acknowledgments. This work was partially supported by the EU LiMoSINe project (288024).