DEIM Forum 2016 C4-6

Query Suggestion for Helping Struggling Search
Zebang CHEN† , Takehiro YAMAMOTO† , and Katsumi TANAKA†† Graduate School of Informatics, Kyoto University36-1 Yoshida-Honmachi, Sakyo-ku, Kyoto, 606-8501 Japan
E-mail: †{chenzb,tyamamot,tanaka}@dl.kuis.kyoto-u.ac.jp
Abstract Search engine users often struggle to find the relevant information for their information need by reformulating
their queries many times. Since many queries during struggling search are failed and sparse, the existing query suggestion
methods often fail to generate effective query suggestions for struggling search. In this paper, we propose a method to generate effective query suggestions aiming to help struggling search. The core is identifying struggling component of on-goingstruggling session and mining the effective representations of it. The struggling component is the semantic unit of information need for which the user struggled to find an effective representation during the struggling session. The proposed method
first identifies the struggling component of given on-going struggling session and mines the sessions containing the identifiedstruggling component from a query log to build a struggling flow graph. The struggling flow graph records the struggling
reformulation behaviors of multiple users for the given struggling component. The experimental results demonstrate that the
proposed method outperforms the existing algorithm in terms of MRR@10 and nDCG@10.
Key words query suggestion, information retrieval, struggling search

1. Introduction

Table 1: Examples of struggling sessions (terms in italics are thestruggling phrase of the query)

Search engines have been widely used to find information andsolutions to problems. However, many users often struggle to locate relevant information to their problem [1]. This search process
is referred to as struggling search. In struggling search, the user
struggles to reformulate query many times for the information. For

Query

Query

Sport Australia history <failed>the donut came from where <failed>Sport of Australia <failed>history of the donut <failed>Sport from Australia <failed>origin of donut <successful>Sport came from Australia <failed>example, Table 1(a) shows a struggling session in which a user attempted to find information about what sports came from Australia.
Unfortunately, although the user attempted to reformulate his/herquery many times, he/she could not locate the required informationand gave up. Hassan et al. reported that, among long search sessions, 36% are struggling sessions and many users fail to locate therequired information [1]. Therefore, it is important for search engines to help users in struggling search effectively.
Query suggestion is an effective way to help a user formulate
query. Many query suggestion methods have been proposed andproven very useful. However, existing query suggestion methods
have limitations when addressing struggling search. One problem
is that most queries in struggling sessions are failed queries withfew clicks, which means that existing methods that rely on query
terms and clicked documents are likely to generate ineffective suggestions and may lead to another failed trial. Another problem isthat the information needs of many struggling sessions are longtail information need, which means that no user or few users havesearched for these information previously, thus, there are no effective related queries in the query log.
In this paper, we propose a query suggestion method aiming tohelp struggling search. The core idea of our method is identi-

(a)

(b)

fying the struggling component of an on-going struggling session
and mining effective representations of the struggling component
to generate query suggestions. The struggling component is a semantic component of the information need in which a user needs tostruggle to find its effective representation (See Section 3). For example, there are three semantic components in the information needof the session shown in Table 1(a): sport, came from, and Australia.
Among these components, user struggled to find effective representations for came from. The same struggling component may occur
in search sessions for different information needs. As shown in Table 1(b), another user attempted to find out where did donut comefrom. This user also struggled to find an effective representation
for came from, similar to the user in Table 1(a). However, this user
finally obtained an effective representation for the struggling component: origin, which can also enable the user in Table 1(a) to locate
relevant information using query: ”sport origin Australia”.
Given an on-going struggling session, we first identify its struggling component and retrieve all sessions with the same struggling
component from a query log. We then build a struggling flow graphby aggregating the struggling reformulation behaviors in the re-the main components of a topic: the textual expression (the querytrieved sesions. Further we can mine effective representations ofor queries), the set of documents relevant to the topic, and the entire

the struggling component to generate effective query suggestions

collection of documents. Aula et al. [11] studied behavioral signals

for the on-going struggling session.

when a user has difficulty with a search task. They found that, when

The contributions of this paper can be summarized as follows.
•••

finding relevant information is difficult, users attempt to formulate

We propose a query suggestion method to help struggling

more diverse queries, use advanced operators more frequently, andsearch. To the best of our knowledge, this is the first query

spend more time on viewing search results pages. Liu et al. [12]suggestion algorithm designed to help struggling search.

explored the effect of task difficulty on search behavior for users

We introduce the concept and a method to identify the strug-with different levels of domain knowledge. Although many stud-

gling component of a struggling session, which enables us toies have been done on understanding task difficulty and how users

understand which part that a user is struggling at.

behave when experiencing difficulty, few studies have attempted to

We introduce the struggling flow graph, which is a graph thatfind ways to assist struggling search. Liu et al. [13] used a learning-records multiple users’ struggling reformulation behaviors for

to-rank approach to rank query suggestions generated using a pre-the same struggling component.

viously proposed method [5] for difficult search, that depends on

The remainder of this paper is organized as follows. In Section

effective click-through data. Odijk et al. [14] studied the charac-

2, we explain related work including query suggestion, struggling

teristics of search tasks where users struggle and proposed ways tosearch, and long-tailed search. In Section 3, we introduce and de-predict future actions and their anticipated impact on search out-

fine the key concepts used in this paper. In Sections 4 and 5, wecomes.

describe how we identify the struggling component and generateLong-tail Search. Yao et al. [15] conducted an empirical study

effective query suggestions, respectively. In Section 6, we explainof user behavior with rare queries using a large-scale query log

our experiment and analyze the results. The paper is concluded inand proved significant differences among many features, including

Section 7.

query length and search results. To generate query suggestions for

2. Related Work

long-tail queries, Bonchi et al. [16] [17] built a center-piece subgraph containing term nodes and query nodes with two types ofQuery Suggestion. One main approach to query suggestion is min-connections: term-query and query-query connections. A random

ing click-through data. Beeferman and Berger [2] built a bipartite

walker starts with the terms in a given query to generate query sug-

graph based on click-through data and clustered queries with thegestions even if the query has not occurred previously. To extend thesame clicked documents because they are likely to have the same

reach of query suggestion for long-tail queries, Szpektor et al. [18]search intent. Baeza-Yates et al. [3] clustered queries based on theirintroduced a query template and an enhanced query flow graph [7]term-weight vector calculated from queries as well as their clickedwith query templates, through which suggestions are available evendocuments. The queries in the same cluster are ranked and con-for the long-tail queries that do not have succeeding query.

sidered possible query suggestions. Mei et al. [4] ranked queries
using the hitting time on the bipartite graph to ensure semantic con-

3. Preliminaries

sistency between the original query and query suggestions. Cao et

In this section, we first explain the conceptes of query log, ses-al. [5] summarized queries and mapped sessions to concepts based

sion, and struggling session used in this paper. We then introduce

on click-through data to build a concept sequence suffix tree, which

the key concepts for modeling struggling search in order to clarify

is used to obtain the context of the current search in order to generate

our approach to generating query suggestions.

context-aware query suggestions. Another main approach to query

Query log: A query log is a log that records user search queries

suggestion is mining query reformulations of search sessions. Boldi

and document clicks with their timestamps. A typical format foret al. [6] used the query flow graph [7] to generate query sugges-a record in a query log is <user id, query, clicked document,

tions. Each node in a query flow graph represents a query and eachtimestamp>. In this paper, we use the AOL query log, which con-edge between two nodes means that they are consecutive in at least

tains the search behaviors of approximately 650,000 users over 3

one session. The short random walk is then applied to the graphmonths, as our primary dataset. Note that the proposed method is

to generate query suggestions. Jones et al. [8] proposed a model tonot specific to the AOL query log, but is applicable to other query

generate a set of query substitutions by replacing the whole querylogs.

or parts of the query with related phrases.

Session: A session represents a topically coherent session during

Struggling Search. Struggling search was first formally introduced

which a user’s information need does not change. One well-known

by Hassan et al. [1]. They analyzed the characteristics of struggling

way to extract sessions from a query log is to use a predefined time

session and proposed a model to distinguish struggling sessions andthreshold, e.g., 30 min of inactivity [19], which may contain search

exploratory sessions [9]. Task difficulty is a main factor that leads

queries and document clicks for different information needs in theto struggling search. Carmel et al. [10] investigated what makes asame session [20]. To ensure that sessions are topically coherent,

query difficult, by capturing and analyzing the relationships among

we used the settings in [1] with a small adjustment: two consecu-

tive queries are topically coherent if they are no longer than 10 min

Table 2: Example components.

apart and they must share at least one non-stopword term. In the rest
parts of this paper, we simply use session to represent a topicallycoherent session.

Component

Representations

gas mileagegas mileage, mpg, fuel mileage, miles per gallon,
kilometer per liter, etc.

Struggling session: A struggling session is a session in which auser experiences difficulty locating information that is relevant tocome fromof, from, come from, originate from, history, etc.

amounthow many, number, count, amount, statistics, etc.

their information need. Typical user search behaviors in a struggling session are reformulating query many times and spending sig-

Table 3: Example struggling session for information need wherenificant time on the search process [1]. Several examples are shown

does donut come from, with components: donut, came from. Terms

in Table 1.

between () are input for representing donut, terms between [] are

Here, we introduce key concepts for modeling struggling search.

input for representing came from.

Information need: An information need is the need to locate infor-

Query

Division based on components

mation in order to satisfy a user’s requirement. Example informa-the donut came from where(the donut) [came from where]tion needs are as follows: what sports came from Australia, where

history of the donut[history of] (the donut)

did donut come from, and gas mileage of 2000 4runner.

origin of donut[origin of] (donut)

Component: A component is a semantic unit that corresponds tothings in the real world, such as concepts, objects, actions, and relations. In this work, we model that an information need comprises a
set of components. For example, the information need what sports
came from Australia comprises three components, sport, came from,and Australia, and the information need gas mileage of 2000 4runner comprises gas mileage and 2000 4runner.
Each component has a set of representations, which are used by
Figure 1: Example of struggling phrase classifier.

users to describe the component in their queries. For example, todescribe the component 2000 4runner, users may use 2000 4runner,

4. Identifying Struggling Phrase

4runner, toyota 4runner, toyota 2000 4runner, etc. More examples
are shown in Table 2.
During a session, users choose a representation for each compo-

In this section, we explain how we identify the struggling phrases
of a struggling session.

nent of their information need based on their own knowledge and4. 1 Problem statement

experience to formulate a query, which means that each term in

Given a struggling session with a sequence of queries, our objec-

the query is an input that describes the corresponding component

tive is to distinguish the struggling phrase in each query. To this end,of their information need. If the returned results do not satisfy the

we take a machine learning approach and build a struggling phrase

information need, users may reformulate the query by changing,classifier. Specifically, for each term in a query of a struggling ses-adding/or removing term(s) in order to locate relevant information,

sion, we classify it into one of two classes, struggling phrase (SP)as shown in Table 3.

and non-struggling phrase (NSP), as shown in Figure 1.

Struggling component: In a struggling session, we define a strug-

4. 2 Features

gling component as a component for which user has difficulty to findTo build the struggling phrase classifier, we designed features foran effective representation. For example, for the session shown in

identifying struggling phrases in a struggling session, as shown in

Table 1(a), the information need of the session is what sports came

Table 4. There are two types of features, i.e., term-level features andfrom Australia, which has three components, sport, came from, andAustralia. During the session, the user frequently reformulated thesession-level features.
• Term-level features: These features describe the characteris-

representation of the came from component, which may mean thattics of a term. A term with many alternatives has higher prob-

the user had difficulty finding an effective representation of thisability to be classified as a struggling phrase because a usercomponent. Thus, came from is the struggling component in thismay struggle to find an effective representation from these al-session.

ternatives. For example, a term that refers to an entity typically

Struggling phrase: Given a query in a struggling session, the strug-

has fewer alternatives. In addition, the part-of-speech of a term

gling phrase of the query is defined as the set of terms in the query

may indicate whether it has many (or few) alternatives to a cer-that represent the struggling component of the session. Note that thetain degree.

struggling phrase of a query may be empty. Table 1 shows exam-•

Session-level features: These features describe the relation-

ples of struggling phrases in a struggling session. For example, theships of a term and the session. A term that the user gives up

struggling phrases of the four queries in Table 1(a) are {history},on quickly has high probability of being classified as a strug-{of}, {from}, and {came, from}.

gling phrase, and a term that the user keeps in all queries inTable 4: Struggling phrase classifier features
Name

Description

Table 5: Example struggling sessions.
Query

Query

Term level features
isEntity

whether the term refers to an entity

POS

part-of-speech of the term

Session level features
occurenceRatio

ratio of queries in which the term occurred2007 lincoln mkz mileage <failed> Honda civic fuel efficiency <failed>2007 lincoln mkz fuel <failed>Honda civic mileage <failed>2007 mkz fuel per mile <failed>Honda civic gas mileage <successful>lincoln mkz mpg <successful>in the session
firstOccurence

(a)

(b)

order number of the query in which the term
first occurred

As can be seem, the classifier outperformed the frequency-based
method in terms of precision. The precision of the classifier increased with an increased number of queries. The precision reached0.76 when the proposed method used all queries in a session. In
contrast, the precision of the frequency-based method did not improve with an increased number of queries. One reason for this isthat a user slightly modified the terms of non-struggling phrase laterin the session.

5. Generating Effective Query Suggestion
In this section, we first explain how we extract sessions that havethe same struggling component as the on-going struggling session.
We then introduce the struggling flow graph, how to build the graph,
Figure 2: Precision of struggling phrase classifier.

and mine effective representations for the struggling component inorder to generate effective query suggestions.

the session has high probability of being classified as a non-

5. 1 Mining sessions with the same struggling component

struggling phrase.

As introduced in Section 3, the struggling component is a compo-

4. 3 Experimental setup

nent of an information need for which user experiences difficulty toData. We manually extracted 146 struggling sessions from the AOL

find an effective representation of the component. The same strug-

query log, which resulted in 540 queries. For each query, we manu-

gling component may occur in sessions with different information

ally labeled terms as a struggling phrase or a non-struggling phrase

needs. We have hypothesized that sessions with the same struggling

by checking the query, the search results, and the context of the ses-component have similar struggling phrases, and share the same ef-

sion, assuming we were the searcher with an information need es-

fective representations for the struggling component. Two examples

timated by the search behavior. We trained the classifier with thesehave been shown in Table 1(a) and Table 1(b), in which the first user

labeled data to distinguish struggling phrases and non-struggling

searched for what sport came from Australia and the second userphrases of a query for a struggling session.

searched for where does donut came from, wherein both struggled

Baseline. For the baseline, we used the frequency-based method toto represent the struggling component came from effectively. Fur-

identify the struggling phrase of a query. This method classifies ather examples are shown in Table 5(a) and Table 5(b), where theterm as a non-struggling phrase only when all queries in the session

first user searched for the gas mileage of 2007 lincoln mkz and thecontain the term; otherwise, the term is was classified as a strug-

second user searched for the gas mileage of Honda civic, and bothgling phrase.

struggled to represent the struggling component gas mileage effec-

Setting. We used the support vector machine with a linear kernel totively.

train the classifier. 10-fold cross-validation was used for this exper-

Figure 3 illustrates how we mine sessions with the same strug-

iment. Note that the performance of the proposed method depends

gling component from the query log. Given an on-going strugglingon the number of queries in a session. To investigate the effect ofsession, we hope to obtain all sessions with the same struggling

the number of queries available for the classifier on classification

component as the given session from the query log. Specifically,

performance, we experimented with several cases by changing the

given an on-going struggling session, we first identify its struggling

number of queries in a session (e.g., the first query, the first two

phrases and retrieve the struggling sessions with the same struggling

queries, the first three queries . . ., all queries).

phrases in their queries from the query log. Then, we again extract

4. 4 Experimental results

the struggling phrases of each retrieved session to obtain more ses-

Figure 2 shows the precision of the classification obtained by thesions with same struggling phrases in a breadth-first-search manner.

proposed method and the frequency-based method. The x-axis is

5. 2 Struggling flow graphthe number of queries used by each method to classify a term.

Having obtained sessions with possibly the same struggling com-and reformulate it as query qj in a topically coherent session. To
generate query suggestions for a given query(ies) q, a random walk
is applied to the query flow graph with the random walker startingwith query(ies) q. We can extract query suggestions according to
the value of the stationary distribution of each query.
We follow the idea of the query flow graph, except for the follow-

Figure 3: Mining sessions with the same struggling component fromquery log.

ing differences.
• The struggling flow graph represents a struggling phrase as anode.
•

The struggling flow graph incorporates information about
whether a query appears to be successful or a failure into thegraph.

For the former point, differing from the query flow graph, which
aggregates all sessions in the query log into a single graph, thestruggling flow graph aggregates only the reformulation behaviors
of terms rather than queries. This allows us to understand the termlevel reformulation behaviors of users, which may address the probFigure 4: Example of struggling flow graph.

lem of long-tailed queries.
For the latter point, the failure rate in struggling search is high,ponent, we then build a struggling flow graph to find the effective representation of the struggling component. The purpose of
the struggling flow graph is to aggregate multiple users’ reformulation behaviors for the terms of a struggling component and minethe effective representations for the given struggling component. A
struggling flow graph extendsthe query flow graph [6]. In the struggling flow graph, each node represents a struggling phrase of the
struggling component. In addition, an edge in the struggling flow
graph means that two struggling phrases are consecutive in at least
one struggling session.
Here, s0 denote an on-going struggling session for which wewant to provide query suggestions, S = {s1 , . . . , sn } denote theset of sessions mined by the method described in Section 5. 1 , andV = {v1 , . . . , vm } denote the unique set of struggling phrases obtained from S by using the classifier described in Section 4.
Formally, the struggling flow graph for sessions S is represented
as weighted directed graph GS = (V, E, ω).
• V is the set of nodes in the graph. Each node corresponds to a•

struggling phrase.
E⊂= V × V is the set of directed edges. If there is at least one
session where two struggling phrases vi and vj appear consecutively in S, there is a directed edge from vi to vj . In addition,for every vi ∈ V there is a self-transitive edge from vi to vi .

•

ω : E → (0..1] is a weighting function that assigns a weightω(vi , vj ) to each pair of struggling phrases (vi , vj ) ∈ E.
5. 3 Finding effective representation using struggling flow
graph
Here, we describe how we find the effective representation of

the struggling component using the Struggling flow graph. As explained previously, the struggling flow graph is an extension of thequery flow graph. In the query flow graph, each node represents aquery q and the weight of an edge between two queries qi and qj
is determined by the probability that the user who issued query qi

which increases the probability of failed query suggestions by the
random walk in the graph. To address this problem, we incorporate
information about whether a query appears successful or a failure
into the graph. Suppose we can predict the effectiveness of eachstruggling phrase in the graph. Our idea is to add high self-transition
probability to the effective struggling phrases. Since a node withhigh self-transition probability is likely to obtain a high random
walk score in the stationary distribution, we expect that adding ahigh self-transition probability to effective struggling phrases willallow us to find effective struggling phrases for the struggling component by applying a random walk to the graph.
5. 4 Preparing transition probabilities
In this subsection, we describe how we compute the transition
probabilities among the nodes in the struggling flow graph. The
assumption behind mining effective struggling phrases is that if
one struggling phrase is effective, most users who input it willstop searching as it is effective in helping the users find relevant
pages with the information they require. Similarly, if one strugglingphrase is ineffective, most users who input it will continue searchingas it fails to help the users find the relevant pages. The actual transition probabilities are computed based on the following method.
Here, e(vi ) represents the number of sessions that end with struggling phrase vi with effective clicks and N (vi , vj ) represents thenumber of sessions where vi and vj occur consecutively. The flow
information of struggling phrases that occur only a few times are
not trustworthy because they are biased due to sparsity. We define
the degree of trustworthiness of a struggling phrase to evaluate howtrustworthy the flow information of the struggling phrase is, whichis represented as td(vi ). As a struggling phrase occurs more times,
the degree of trustworthiness of it increases.

∑td(vi ) =e(vi )
vj ∈V N (vj ,si ), if e(si ) < threshold

Table 6: Examples sessions.
.


1.0,

Strugglig component Example session

if e(vi ) >= thresholdq1 : 2001 mustang fuel per mile

The self-transition probability of a node is set as follows.
ω(vi , vi ) = td(vi ) ∑gas mileage of car

q3 : 2001 mustang gasoline milese(vi ).
vk ∈V N (vj , vi )q1 : where does the name bonnaroo come fromorigin of something

For the rejected self-transition probability due to low trustable de-q1 : top 25 children hospital

struggling flow graph as random jump probability rj(vi ).
best of somethinge(vi )

vj ∈V N (vj , vi )q2 : top 25 children’s hospitalq3 : number one children’s hospital.

The weight between different struggling phrases vi and vj (i =| j)q2 : bonnaroo hisotry
q3 : bonnaroo history

gree, we averagely distribute them to all struggling phrases in therj(vi ) = (1 − td(vi )) ∑q2 : 2001 mustang fuel efficiency

the AOL query log. For each struggling component, we manually
extracted as many struggling sessions with the struggling compo-

is as follows:

nent as possible from the AOL query log. Finally, for each strug-r(vi , vj )rj(vi )
ω(vi , vj ) = (1 − ω(vi , vi ) − rj(vi )) ∑
+
.
r(v
,
v
)
|V |
i
k
vj ∈V

gling component, we randomly sampled 10 struggling sessions from

Note that the weights calculated based on above weighting func-

in total). Table 6 shows examples of struggling components andtions w(·) are already normalized such that their values represent

their corresponding session.

the transition probability among nodes. In addition, note that, the6. 3 Ground truth

the extracted sessions and used them in the experiment(80 sessions

struggling flow graph uses uniform random jump rather than biased

We defined a query suggestion that enables a user to locate rele-

random jump, as is the case of the query flow graph, because ourvant pages as an effective suggestion. To create ground truth query

struggling flow graph consists of only related sessions, i.e., sessions

data, for each session described in the previous subsection, we firstwith the same struggling component.

simulated the session user and attempted to understand the user’s

5. 5 Generating query suggestions

search intent as best as possible. For each of the top 10 query sug-

Here, we describe the overall method to generate query sug-gestions generated by a method, we issued the suggestion to a com-

gestions for a given on-going session. Given an on-going session

mercial search engine and examined whether there were relevant

s0 = {q1 , . . . , qn }, where n represents the number of queries in thepages for the user’s information need in the first page of the searchsession, we first identify the struggling phrases of the session using

results. If there was at least one relevant document in the search

the method described in Section 4. We then mine the set of sessions

results page, the suggestion was considered effective; otherwise theS using the method described in Section 5. 1 and build the strug-suggestion was considered ineffective.

gling flow graph GS . Then, we apply a random walk to the graph

6. 4 Evaluation metrics

and extract the top k nodes according to their random walk values in

The following metrics were employed to measure the perfor-

stationary distribution. Finally, we generate the query suggestions

mance of query suggestions.
• Support rate: The ratio of sessions for which at least one

by replacing the struggling phrases of the last query in the on-going

query suggestion could be offered.

sessions with the top k struggling phrases.

6. Experiment
In this section, we introduce an experiment conducted to evaluate
the effectiveness of the query suggestions generated by the proposed
method.
6. 1 Baseline•

Effective support rate@10: The ratio of sessions in which
one or more effective query suggestions were offered in the top
10 query suggestions.

•

MRR@10: Mean reciprocal rank (MRR) of the top 10 querysuggestions.

•nDCG@10: Normalized discounted cumulative gain (nDCG)

For the baseline, we used the query flow graph proposed by Boldiof the top 10 query suggestions. Here, we used binary rele-

et al. [7]. The query flow graph is a directed graph that aggregatesvance for the evaluation. An effective query suggestion had

a query log and has been proven very useful for query suggestions

relevance of 1, while an ineffective query suggestion had rele-and user behavior analysis. Here, we refer to the baseline method asvance of 0.

query flow graph method and the proposed method with the strug-

6. 5 Setting

gling flow graph method.

We used all the prepared labeled struggling sessions prepared

6. 2 Evaluated sessions(Section 4.2) to train the struggling phrase classifier, which was usedTo evaluate the effectiveness of the proposed method with diverse

to detect struggling phrases of a session. In addition, as with the ex-

struggling sessions, we first manually prepared eight types of strug-

periment explained in Section 4. 3, we experimented with several

gling components by scanning the struggling sessions sampled fromcases by changing the number of available queries in a session.

Table 7: Example struggling sessions
Query

Query

q1 : average mileage for ford mustang

q1 : history of baseballq2 : 99 mustang mileageq2 : country and origin of baseball

(b)

(a)

Table 8: Query suggestions for struggling session in Table 7(a).
Suggestions

Suggestions

Not available.

1st: 99 mustang gas mileage
2nd: 99 mustang mileage rate

Figure 5: Mean support rate

3rd: 99 mustang fuel mileage
4th: 99 mustang distance
5th: 99 mustang mileage deduction(a) Suggestion by baseline.

(b) Suggestion by proposed method.

sessions even when it could use all queries in the session. Thiswas primarily because information needs for many struggling sessions are long-tailed; thus, the queries in struggling search are also
long-tailed queries, which may never occur in the query log. On theother hand, the struggling flow graph could generate query suggestions for significantly more sessions than the query flow graph. This

Figure 6: Mean effective support rate@10

shows that considering struggling phrases in a session rather than
the queries themselves allows us to address the problem of longtailed queries. Figures 6, 7, and 8 summarize the mean effective
support rate@10, MRR@10 and mean nDCG@10, respectively.
From Figure 6, we can observe that the effective support rate@10 ismuch lower than the support rate for both the query flow graph andthe struggling flow graph, which means that only a portion of thesessions were provided effective query suggestions among the sessions for which the given method could provide query suggestions.
Similar to the support rate, the struggling flow graph outperformed
the query flow graph significantly relative to generating effective

Figure 7: MRR@10

query suggestions. The struggling flow graph generated effective
query suggestions for 35% of the sessions, and the query flow graphgenerated effective query suggestions for only 7.5% of the sessions,even when it used all queries of the sessions. From Figures 7 and 8,
we can see that the ranking performance increased with an increasing number of available queries for both the query flow graph andthe struggling flow graph. The struggling flow graph also outperformed the query flow graph in terms of the ranking performance ofeffective query suggestions. When using all queries in the session,
the proposed method achieved MRR@10 of 0.113 and nDCG@10

Figure 8: Mean nDCG@10
6. 6 Resultsof 0.166, and the baseline method achieved MRR@10 of 0.043 andnDCG@10 of 0.058.
Two detailed examples of struggling sessions used in the experi-

Figure 5 shows the mean support rate obtained by the baseline

ment are shown in Table 7(a) and Table 7(b). For the struggling ses-method and the proposed method. As can be seen, the performancesion shown in Table 7(a), the user struggled to find the gas mileage

to generate query suggestions for struggling sessions improved asof ford 99 mastang. The query suggestions generated by query flow

the number of available queries increased for both the query flow

graph are shown in Table 8(a), and those generated by the struggling

graph and the struggling flow graph. However, the query flow graphflow graph are shown in Table 8(b). As can be seen, no query sug-

could not generate any query suggestion for 69% of the struggling

gestion was generated by the query flow graph because the queries

Table 9: Query suggestions for struggling session in Table 7(b).
Suggestions

Suggestions

1st: history of futball

1st: baseball history

2nd: history of lacrosse

2nd: baseball origin

3rd: baseball history

3rd: baseball origin game

4th: history of American futball

4th: baseball mean

5th: history of baseball and steroids

5th: baseball begin(a) Suggestion by baseline.

(b) Suggestion by proposed method.

in the session shown in Table 7(a) never occurred in the query log

[4]
[5]

[6]

[7]

because the information need of the session was a long-tailed information need. For the struggling flow graph method, we first distin-[8]

guish the struggling component of the session and then mine the effective struggling phrases to generate query suggestions, that maybe
effective for the user’s information need.
Another example struggling session is shown in Table 7(b), where
the user struggled to find information about the origin of baseball.

[9]
[10]
[11]

The query suggestions generated by the query flow graph are shownin Table 9(a), and the query suggestions generated by the struggling[12]

flow graph are shown in Table 9(b). Several query suggestions weregenerated by the query flow graph; however, none were effective
because they were either failed queries for the same information[13]

need or a query for another information need. As noted previously,
most queries in a struggling session are failed queries and the query[14]

flow graph aggregates all information from a query log and does
not guarantee consistency of the information need. The struggling
flow graph method only retrieved sessions that with potentially thesame struggling component, which guarantees consistency to some[15]

degree and helps to generate several query suggestions that may satisfy the user’s information need.

[16]

7. Conclusion[17]

In this paper, we proposed a query suggestion method to help
struggling search based on identifying the struggling componentof a struggling session and mine effective representations using a[18]

struggling flow graph. We conducted an experiment to investigate
the effectiveness of the proposed method compared to a baseline.
The experimental results show that the proposed method outperformed the baseline method in terms of support rate, effective support rate@10, MRR@10, and nDCG@10. In the future, we plan
to improve the model for identifying the struggling phrase and examine methods to improve the prediction of the user’s informationneed.
Acknowledgement

This work was supported in part by KAK-ENHI (#15H01718).
References[1] Ahmed Hassan, Ryen W White, Susan T Dumais, and Yi-Min Wang.
Struggling or exploring?: disambiguating long search sessions. In
WSDM’14, pages 53–62, 2014.
[2] Doug Beeferman and Adam Berger. Agglomerative clustering of asearch engine query log. In KDD’00, pages 407–416, 2000.
[3] Ricardo Baeza-Yates, Carlos Hurtado, and Marcelo Mendoza. Query

[19]
[20]

recommendation using query logs in search engines. In Current
Trends in Database Technology-EDBT 2004 Workshops, pages 588–
596, 2005.
Qiaozhu Mei, Dengyong Zhou, and Kenneth Church. Query suggestion using hitting time. In CIKM’08, pages 469–478, 2008.
Huanhuan Cao, Daxin Jiang, Jian Pei, Qi He, Zhen Liao, EnhongChen, and Hang Li. Context-aware query suggestion by mining clickthrough and session data. In KDD’08, pages 875–883, 2008.
Paolo Boldi, Francesco Bonchi, Carlos Castillo, Debora Donato, andSebastiano Vigna. Query suggestions using query-flow graphs. In
Workshop on Web Search Click Data, pages 56–63, 2009.
Paolo Boldi, Francesco Bonchi, Carlos Castillo, Debora Donato,
Aristides Gionis, and Sebastiano Vigna. The query-flow graph:model and applications. In CIKM’08, pages 609–618, 2008.
Rosie Jones, Benjamin Rey, Omid Madani, and Wiley Greiner. Generating query substitutions. In WWW’06, pages 387–396, 2006.
Gary Marchionini. Exploratory search: from finding to understanding. Communications of the ACM, 49(4):41–46, 2006.
David Carmel, Elad Yom-Tov, Adam Darlow, and Dan Pelleg. Whatmakes a query difficult? In SIGIR’06, pages 390–397, 2006.
Anne Aula, Rehan M Khan, and Zhiwei Guan. How does search behavior change as search becomes more difficult? In CHI’10, pages
35–44, 2010.
Chang Liu, Jingjing Liu, Michael Cole, Nicholas J Belkin, and Xiangmin Zhang. Task difficulty and domain knowledge effects on information search behaviors. In ASIST’12, 49(1):1–10, 2012.
Yang Liu, Ruihua Song, Yu Chen, Jian-Yun Nie, and Ji-Rong Wen.
Adaptive query suggestion for difficult queries. In SIGIR’12, pages
15–24, 2012.
Daan Odijk, Ryen W. White, Ahmed Hassan Awadallah, and Susan T. Dumais. Struggling and success in web search. In Proceedingsof the 24th ACM International on Conference on Information andKnowledge Management, CIKM ’15, pages 1551–1560, New York,NY, USA, 2015. ACM.
Ting Yao, Min Zhang, Yiqun Liu, Shaoping Ma, and Liyun Ru. Empirical study on rare query characteristics. In WI’11, pages 7–14,
2011.
Francesco Bonchi, Raffaele Perego, Fabrizio Silvestri, Hossein Vahabi, and Rossano Venturini. Recommendations for the long tail byterm-query graph. In WWW’11, pages 15–16, 2011.
Francesco Bonchi, Raffaele Perego, Fabrizio Silvestri, Hossein Vahabi, and Rossano Venturini. Efficient query recommendations in
the long tail via center-piece subgraphs. In SIGIR’12, pages 345–
354, 2012.
Idan Szpektor, Aristides Gionis, and Yoelle Maarek. Improving recommendation for long-tail queries via templates. In WWW’11, pages
47–56, 2011.
Ryen W White and Susan T Dumais. Characterizing and predicting
search engine switching behavior. In CIKM’09, pages 87–96, 2009.
Rosie Jones and Kristina Lisa Klinkner. Beyond the session timeout:
automatic hierarchical segmentation of search topics in query logs.
In CIKM’08, pages 699–708, 2008.