09-05-2013, 02:20 PM
Organizing User Search Histor
Organizing User.pdf (Size: 660.51 KB / Downloads: 31)
Abstract
Users are increasingly pursuing complex task-oriented goals
on the Web, such as making travel arrangements, managing finances
or planning purchases. To this end, they usually break down the tasks
into a few co-dependent steps and issue multiple queries around these
steps repeatedly over long periods of time. To better support users in
their long-term information quests on the Web, search engines keep
track of their queries and clicks while searching online. In this paper, we
study the problem of organizing a user’s historical queries into groups
in a dynamic and automated fashion. Automatically identifying query
groups is helpful for a number of different search engine components
and applications, such as query suggestions, result ranking, query alterations,
sessionization, and collaborative search. In our approach, we
go beyond approaches that rely on textual similarity or time thresholds,
and we propose a more robust approach that leverages search query
logs. We experimentally study the performance of different techniques,
and showcase their potential, especially when combined together.
INTRODUCTION
AS the size and richness of information on the Web
grows, so does the variety and the complexity of
tasks that users try to accomplish online. Users are no
longer content with issuing simple navigational queries.
Various studies on query logs (e.g., Yahoo’s [1] and
AltaVista’s [2]) reveal that only about 20% of queries
are navigational. The rest are informational or transactional
in nature. This is because users now pursue much
broader informational and task-oriented goals such as
arranging for future travel, managing their finances, or
planning their purchase decisions. However, the primary
means of accessing information online is still through
keyword queries to a search engine. A complex task
such as travel arrangement has to be broken down into a
number of co-dependent steps over a period of time. For
instance, a user may first search on possible destinations,
timeline, events, etc.
Query (or Query Group) Relevance.
To ensure that each query group contains closely related and relevant
queries and clicks, it is important to have a suitable relevance
measure sim between the current query singleton
group sc and an existing query group si 2 S. There
are a number of possible approaches to determine the
relevance between sc and si. Below, we outline a number
of different relevance metrics that we will later use as
baselines in experiments (see Section 5). We will also
discuss the pros and cons of such metrics as well as our
proposed approach of using search logs (see Section 3).
Time. One may assume that sc and si are somehow
relevant if the queries appear close to each other in
time in the user’s history. In other words, we assume
that users generally issue very similar queries and clicks
within a short period of time. In this case, we define the
following time-based relevance metric simtime that can
be used in place of sim in Figure 3.
QUERY RELEVANCE USING SEARCH LOGS
We now develop the machinery to define the query
relevance based on Web search logs. Our measure of
relevance is aimed at capturing two important properties
of relevant queries, namely: (1) queries that frequently
appear together as reformulations and (2) queries that
have induced the users to click on similar sets of pages.
We start our discussion by introducing three search
behavior graphs that capture the aforementioned properties.
Following that, we show how we can use these
graphs to compute query relevance and how we can
incorporate the clicks following a user’s query in order
to enhance our relevance metric.
Search Behavior Graphs
We derive three types of graphs from the search logs
of a commercial search engine. The query reformulation
graph, QRG, represents the relationship between a pair
of queries that are likely reformulations of each other.
The query click graph, QCG, represents the relationship
between two queries that frequently lead to clicks on
similar URLs. The query fusion graph, QFG, merges the
information in the previous two graphs. All three graphs
are defined over the same set of vertices VQ, consisting
of queries which appear in at least one of the graphs,
but their edges are defined differently.
Query Reformulation Graph
One way to identify relevant queries is to consider query
reformulations that are typically found within the query
logs of a search engine. If two queries that are issued
consecutively by many users occur frequently enough,
they are likely to be reformulations of each other. To
measure the relevance between two queries issued by
a user, the time-based metric, simtime, makes use of the
interval between the timestamps of the queries within
the user’s search history. In contrast, our approach is
defined by the statistical frequency with which two
queries appear next to each other in the entire query
log, over all of the users of the system.
QUERY GROUPING USING THE QFG
In this section, we outline our proposed similarity function
simrel to be used in the online query grouping
process outlined in Section 2. For each query, we maintain
a query image, which represents the relevance of
other queries to this query. For each query group, we
maintain a context vector, which aggregates the images
of its member queries to form an overall representation.
We then propose a similarity function simrel for two
query groups based on these concepts of context vectors
and query images. Note that our proposed definitions of
query reformulation graph, query images, and context
vectors are crucial ingredients, which lend significant
novelty to the Markov chain process for determining
relevance between queries and query groups.
Combining the Methods
The results of the previous experiment point out the contrast
between the performance of the different methods.
This suggests that a combination of two methods may
yield better performance than either method individually.
We explore combining two methods by merging the
output query groups as follows: given the output groups
of any two methods, query pairs that belong to a group
within one or within the other, will belong to the same
group in the combined output.
Table 2 shows the performance gained by combining
QFG with each baseline. For QFG+Jaccard and
QFG+Levenshtein, the combination performs better than
the individual methods. QFG+Time performs better than
Time but worse than QFG.
RELATED WORK
While we are not aware of any previous work that
has the same objective of organizing user history into
query groups, there has been prior work in determining
whether two queries belong to the same search task.
In recent work, Jones and Klinkner [4] and Boldi et
al. [5] investigate the search-task identification problem.
More specifically, Jones and Klinkner [4] considered a
search session to consist of a number of tasks (missions),
and each task further consists of a number of sub-tasks
(goals). They trained a binary classifier with features
based on time, text, and query logs to determine whether
two queries belong to the same task. Boldi et al. [5]
employed similar features to construct a query flow
graph, where two queries linked by an edge were likely
to be part of the same search mission.
Our work differs from these prior works in the following
aspects. First, the query-log based features in [4],
[5] are extracted from co-occurrence statistics of query
pairs. In our work, we additionally consider query pairs
having common clicked URLs and we exploit both cooccurrence
and click information through a combined
query fusion graph. [4] will not be able to break ties
when an incoming query is considered relevant to two
existing query groups. Additionally, our approach does
not involve learning and thus does not require manual
labeling and re-training as more search data come in;
our Markov random walk approach essentially requires
maintaining an updated query fusion graph. Finally, our
goal is to provide users with useful query groups onthe-
fly while respecting existing query groups. On the
other hand, search task identification is mostly done at
server side with goals such as personalization, query
suggestions [5] etc.
CONCLUSION
The query reformulation and click graphs contain useful
information on user behavior when searching online.
In this paper, we show how such information can be
used effectively for the task of organizing user search
histories into query groups. More specifically, we propose
combining the two graphs into a query fusion
graph. We further show that our approach that is based
on probabilistic random walks over the query fusion
graph outperforms time-based and keyword similaritybased
approaches. We also find value in combining our
method with keyword similarity-based methods, especially
when there is insufficient usage information about
the queries. As future work, we intend to investigate the
usefulness of the knowledge gained from these query
groups in various applications such as providing query
suggestions and biasing the ranking of search results.