一般論文

Rank Optimizationof Personalized Search
Lin LI♥
Zhenglu YANG♦
Masaru KITSUREGAWA♠

Augmenting the global ranking based on the linkage
structure of the Web is one of the popular approaches indata engineering community today for enhancing thesearch and ranking quality of Web information systems.
This is typically done through automated learning of userinterests and re-ranking of search results throughsemantic based personalization. In this paper, we propose
a query context window (QCW) based framework for
Selective uTilization of search history in personalized
leArning and re-Ranking (STAR). We conduct extensive
experiments to compare our STAR approach with the
popular directory-based search methods (e.g., Google
Directory search) and the general model of most existing
re-ranking schemes of personalized search. Our
experimental results show that the proposed STARframeworkcaneffectively
captureuser-specificquery-dependent personalization and improve theaccuracy of personalized search over existing approaches.

1. Introduction
Encoding human search experiences and personalizing
the search result delivery through ranking optimization isa popular approach to enhance Web search. Although thegeneral Web search today is still performed and delivered
predominantly through search algorithms, e.g., Google’s
PageRank [17] based query independent ranking
algorithms, the interests in improving global notion ofimportance in ranking search results by creating
personalized view of importance have been growing over
the recent years. We categorize the research efforts on
personalized search into three classes of strategies: 1)
query modification or augmentation [3], [26], 2) link-based
score personalization [8], [9], [15], [17], [19], [22], and 3)
search result re-ranking [4], [5], [12], [14], [26], [29], [30].
A general process of re-ranking is to devise efficientmechanisms to re-order the search result ranking using
the global importance by personalized ranking criteria.
♥ Dept. of Information and Communication Engineering,
University of Tokyolilin@tkl.iis.u-tokyo.ac.jp♦ Institute of Industrial Science, University of Tokyoyangzl@tkl.iis.u-tokyo.ac.jp♠ Regular Member Institute of Industrial Science,
University of Tokyo
kitsure@tkl.iis.u-tokyo.ac.jp

DBSJ Journal, Vol.8, No.1
June 2009
Such criteria are typically derived from the modeling ofusers’ search behavior and interests.
In this paper, we develop a rank optimization
framework that promotes Selective uTilization of searchhistory for personalized leArning and re-Ranking (STAR).
Our STAR framework consists of three design principles
and a suite of algorithms for learning and encoding user’s
short-term and long-term search interests and re-rankingof search results through a careful combination of recent
and previous search histories. We show that even though
short-term interests based personalization using the mostrecent search histories may be effective at times [15], [25],[26], it is generally unstable and fails to capture thechanging behavior of the users. Furthermore, most of
existing long-term interests based personalization using
the entire recent and previous search histories fails to
distinguish the relevant search history from irrelevant
search history [4], [18], [30], making it harder to be aneffective measure alone for search personalization.
Bearing in mind of these observations, our STARframework advocates three design principles for rank
optimization. First, we devise a so-called query context
window (QCW) model to capture the user’s searchbehavior through a collection of her per-query based
click-through data. Second, we develop a query-to-query
similarity model to distinguish the relevant searchmemories of personalized search behavior from irrelevant
ones in the QCW of each user, reducing the noises
incurred by using either a recent fragment or the entire
QCW. Third, we develop a fading memory based weightfunction to carefully combine the frequency of relevant
search behavior (long term interests) with the most recent
search behavior (short term interests). To show theeffectiveness of our STAR framework in quality
enhancement of personalized search, we propose lengthand depth based hierarchical semantic similarity metrics
and compare the effectiveness of four re-ranking
strategies: 1) naive re-ranking that is query and time
independent; 2) relevant search memory based re-ranking
that is query dependent but time independent; 3) fading
memory based re-ranking that is time dependent but
query independent; and 4) hybrid re-ranking that is bothquery and time dependent. Our experiments show thatthe hybrid re-ranking scheme can effectively combine theprevious and recent memories through a smooth andgradually fading memory based weighting function. More
importantly, our experimental results show that the
proposed STAR framework for personalized search andre-ranking
caneffectively
captureuser-specificquery-dependent personalization preference and improve
the accuracy of personalized search over the popular
directory-based search methods (e.g., Google Directory
search) and the general model of most existing re-ranking
schemes of personalized search.
The remainder of this paper is organized as follows. The
overview of our STAR framework is presented in Section 2.
Then, we discuss building QCW-based user profiles anddesigning re-rank strategies in Section 3 and Section 4
respectively. Experimental results will be given in Section
5. Related works are reviewed in Section 6. Finally, we
conclude the paper in Section 7.

日本データベース学会論文誌 Vol.8, No.1
2009 年 6 月

一般論文

DBSJ Journal, Vol.8, No.1
June 2009

2. The STAR Framework Overview
The goal of the STAR framework is to design a semanticrich user profile model to capture the query context andthe search behavior of each user and intelligently utilize
such user profiles to enhance the quality of personalized
search by effectively re-ranking of the search results
returned from a general purpose search engine. Figure 1
gives a sketch of the STAR framework, consisting of threemain components.
The first component is the text classification modulethat performs hierarchical Web page classification. The
popular way is to classify the documents into a
directory-based ontology, such as Yahoo! Directory [11],ODP (http://dmoz.org) [27], and so on. Studies [1], [10],[16] preferred to building their own ontology. Thanks forthe fact that hierarchical text classification is well studied
in the field of text processing, in the first prototype designof our STAR framework we directly utilize the classified
search results from Google Directory search.
The second component is the context aware learning ofuser’s search behavior. We utilize the per-query based
click-through data to capture query dependent context
and search behavior and develop the query context
window (QCW) model to encode such leaning process. By
automatically generating QCW based user query profiles,
the user learning module automatically captures thequery dependent context of user search behavior. For
example, our approach focuses on the user’s visited search
results (Web pages) which supply us with not only whatkind of content a user is interested in (topics) but also howmuch the user is interested in them (click frequency).
The third component is the query and time dependent,
hybrid re-ranking scheme that produces a newuser-centric, query dependent rank list for each user
query through three step process. First, it selects therelevant click records from the entire QCW of a user
through the query-to-query similarity analysis. Second, it
combines the recent search memories with the previous
search memories through applying a fading memory
based weighting function over the selected QCW clickrecords of a user. Finally, it employs hierarchicalsemantic similarity measures to compute the personalized
ranking of the search results returned from a generalsearch engine. In the subsequent sections we will focus on
the technical detail of the user learning module and there-rank module.

3. QCW Based User Learning Module
Our STAR framework devises the query context window(QCW) to encode the user specific and query dependent
search behavior. Given a user, her query context window
consists of m query-dependent context click records,
denoted as u1, u2, . . . , um. Each click record in the QCW is
composed of the submitted query, the topics associatedwith the click search results, the click frequency of each
topic, and the returned search results of the given query.
The topics are extracted from Google Directory,
structured as a hierarchical tree, so that each click record
has its own tree. This topic tree records the click behaviorof a user on a specific query, which can tell us what kindtechnical details of click record selection are in the next

Figure 1 Overview of the STAR framework
section. Moreover, we implement each QCW as a queue.
The tail of the queue holds most recently requested
queries, while its head holds the least recently requested
queries. When a new query is submitted, thecorresponding record is added to the tail of the queue andthe user model (QCW) is updated accordingly. This queue
keeps the chronological order of different click records,
which can easily differentiate the recent and old searchhistories for re-ranking strategies.
Figure 2 shows an example of QCW with three context
records, each corresponds to one query and its context
encoding of the query dependent click-through data. For
example, a user inputs a query “Disneyland” to Google
Directory search engine, and then input query“Disneyland” as a root node followed by the clicked topics.
The search results are kept in the SRB. Node F isrepresented by the [Theme\Parks, 6] which means the user
has clicked some search results associated with the topic“Theme\Parks” six times in this search. In addition, for each
topic, we store the top four depth of its full path in Google
Directory in a record. For example, the node F is actuallystored as the [\Recreation\ThemeParks].

4. The Re-rank Module
The QCW based re-ranking module needs to address three
key challenges: (1) how to select relevant context records
from the entire QCW given a user query (Section 4.1); (2)whether all the selected query-relevant context records
play the same role in re-ranking the search results of thecurrent query (Section 4.2); (3) how should we re-order the
search results (Section 4.3 and 4.4)? We use calligraphic
upper-case alphabets to represent sets. The elements of a
set are denoted by lower case alphabets. For example, U is
the set of click records in QCW and ui is an element (clickrecord) of U. |U| is the cardinality of the set U.

4. 1 Selecting Relevant Click Records
Given a new input query, we first select the relevant QCWclick records where the encoded queries are similar to thecurrent input query by using a query-to-query similarity
measure. Estimating the similarity (relatedness) between

日本データベース学会論文誌 Vol.8, No.1
2009 年 6 月

一般論文

DBSJ Journal, Vol.8, No.1
June 2009

Figure 2 Query Context Window: click records are queued up in a chronological order
queries has a long history in traditional Information
Retrieval [6], [21], [32]. It is still hot and active in various
topics of Web Information Retrieval [2], [7], [31]. Up to
now it has not been possible to prove that any of thesemeasures outperforms all others in a large set ofexperiments [33].
The similarity between the two queries can be induced
from the overlap of the two lists of search results (URLs)
returned. Clearly, the query-result-vectors present a
better similarity metric than query term-vectors [21]. As
thus, we formally define the query-to-query similarity
measure as follows:

SRB ui ∩ P qin
Q(q , qin ) =SRB ui ∪ p qin

(1)

ui

q ui from
We can get the URL set of search results ofthe search result buffer

SRB ui of the click record u i ,and the URL set of search results

P qin of qin from thecurrent search. The similarity between the two queries is
estimated to the fraction of the intersection of the two
URL sets. In our experiments, URL similarity ismeasured by their host name. We would like to note that
our STAR framework can easily incorporate othersimilarity and specificity measures.

4. 2 Weighing Relevant Click Records
The selected click records are the collection of user’s
previous and recent search behaviors which reflect her
interests. We assume that the user’s interests will
gradually decay as time goes on, so we assign moreweights to more recent QCW click records and decreasing
weights to older QCW click records to further improve theaccuracy of the personalized search using a fading
memory based weight function, defined as follows:

F (u i ) = e

−

log 2
⋅(|U |− i )hf ⋅|U |4. 3 Capturing Search Interests
After the relevant QCW click records and their weights
are determined by Equation 1 and 2, the topics in these
QCW click records are reflecting the user’s current searchinterests. Now we can devise a re-ranking mechanism tore-order the search results by putting those that are moresimilar to the selected topics closer to the top of the final
re-ordered rank list. In our STAR framework, the topics
in the relevant QCW click records are structured in asemantic concept hierarchy as shown in Figure 2.
Hierarchical similarity measures can be used to assess
the similarity between the related topics and the search
results of the given query. Let h be the depth of thesubsumer (the deepest node common to two nodes), l be
the shortest path length between two topics, and M be
the maximum depth of topic directory possessed by a
QCW click record.
Two combinations of depth and length based similarity
measure defined as follows:c1 ≡ HS (t j i , p k in ) =uis set in the range [0.1, 1]. After the click record ui isselected as relevant according to Equation 1, its effect on
the quality of personalized search depends on its temporalorder. With increasing the value of hf, the rate of fading
becomes slow and the weights on previous memories
increase. This fading memory function unifies the user’s
long-term and short-term interests encoded in the QCWclick records by assigning different weights to these clickrecords appearing in different temporal order.

2⋅h1+ 2 ⋅ hc 2 ≡ HS ((t j i , p k in ) = e −0.2⋅l ⋅
u

q

(3)

e 0.6⋅h − e −0.6⋅he 0.6⋅h + e −0.6⋅h(4)Equation 3 is a simple linear transformation function of
the length and the depth, while Equation 4 transfers thelength and the depth by a nonlinear function and then
combines them by multiplication [13].
A QCW click record may record more than one topic
depending a user’s click behavior. We further define thesimilarity between a QCW click record ui and a search
resultpkqin as:s (u i , p kqin ) =(2)

where hf is a half fading parameter. In our experiments, hf

q

HS (t uji ⋅ p kqin ) ⋅ c uji
1∑| T ui | t uji ∈T ui∑ c uji(5)c uj i ∈C u iwhere each topic

c

ui
j

t

ui
j

is weighted by its corresponding

using the click frequency of the topic

j . We further

normalize the sum of hierarchical similarity scores
through dividing it by the number of topics stored in aclick record.

4. 4 QCW Based Re-ranking
In this section we will describe four strategies to re-orderthe search results of her current query.

日本データベース学会論文誌 Vol.8, No.1
2009 年 6 月

一般論文
1)

DBSJ Journal, Vol.8, No.1
June 2009

Strategy 1 − Query and time independent scheme1s1 (U , p ) =s (ui , p kqin )∑| U | ui ∈Uqink

5. Experiments

5. 1 Experiment Setup and Evaluation Measure(6)“Strategy 1” is query and time independent, a naive
strategy. Click records of different past queries are
assigned equal weights regardless of the current input
query. The similarity scores of past queries with a search
result are summed together and divided by the number ofclick records (|U|) in U. “Strategy 1” thinks all the pasthistories (click records) are related to a user’s current
query. As we discussed in Section 1, the entire QCW
includes noisy memories unrelated to the current query.
Most of re-ranking based Web search personalization
methods in the literature [4], [5], [12], [14], [18], [26], [27],[30]. “Strategy 1” can represent the general idea of thesemethods, compared with the following three strategies.
2) Strategy 2 − Query dependent schemes2 (U , pkqin ) =1
Q(q ui , qin ) ⋅ s(ui , pkqin )∑| U | ui ∈U(7)

We define the “Strategy 2” as a query dependent and time
independent strategy, which is selective about by using
Equation 1 to weight these click records. Tan et al. [29]did preliminary discussion on query-dependent selectionof user profile. However, their work is in the context of
only exploiting long-term search histories of users andignores the changes of user’s interests with time.
3) Strategy 3 − Time dependent schemes3 (U , p kqin ) =1
F (ui ) ⋅ s(u i , p kqin )∑| U | ui ∈U(8)“Strategy 3” strengthens recent memories and weakens
the effect of previous memories by applying Equation 2 toeach QCW click record without the selection of relevant
contexts in terms of the input query like “Strategy 2”. If
hf is set to a very small value, the previous memories
cannot have an influential effect on re-ranking.
Researches [15], [25], [26] emphasize that the most recent
search is most directly close to the user’s current
information need, which can be regarded as a special casewhere hf is close to zero in “Strategy 3”.
4)Strategy 4 − Query and time dependent scheme1s1 (U , p ) =∑ F (ui ) ⋅ Q(q ui , qin ) ⋅ s(ui , pkqin ) (9)| U | ui ∈Uqink“Strategy 4” is query and time dependent, a hybrid
strategy. As we know, users have their own
characteristics of search behavior. To handle the mostgeneral case where we have many kinds of Web users andusers will how different search behaviors, “Strategy 4” isdesigned to select relevant click records by Equation 1,
but also assign greater weights to the more recent clickrecords Equation 2.
Given one of the four strategies, a new relevant scorewill be calculated for each of search results. We output thelist of the search results in order of their assigned scores.
In the following experiments, we will evaluate theeffectiveness of the above four re-rank strategies.

The goal of this paper is to achieve a personalized ranking
by scoring the similarity between a user profile and thereturned search results. Instead of creating our own Web
search engine, we retrieve results from Google Directory
search engine and use them as a baseline in the following
evaluation. Moreover, as discussed in [23], informational
queries (IQ) are such queries where the user does nothave a special page in mind and intends to find out Web
pages related to a topic. We further classified the goal of
IQ into three categories: new IQ, semi-new IQ, andrepeated IQ. A query is a new IQ if a user never searches
such a topic before. It means that we cannot get therelevant search histories. A semi-new IQ has similar
topical contents with some of the user’s search histories. A
repeated IQ refers to the query by which the user has
already obtained the desired information, and issearching for it again. The following experiments will
evaluate the performances of the semi-new and repeated
IQs since our STAR framework wants to use the previous
relevant memories to enhance the current search. For new
IQs, collaborative information retrieval will be aninteresting direction in our future work.
The evaluation of our framework is a challenge because
currently there are no suitable query log data sets as apublic benchmark. We created our own real dataset [12]which was collected over a ten-day period (From October
23rd, 2006, to November 1st, 2006). Twelve users areinvited to search through our framework and judge
whether the clicked results are relevant or not. Users
were asked to input search queries related to theirprofessional knowledge in the first four days, and search
queries related to their hobbies in the next three days.
Then, in the last three days, each user is requested torepeat some searches with the queries entered in theprevious days. We got a log of about 300 queries averaging
25 queries per subject and about 1200 records of the pages
the users clicked in total. The size of this real data set isrelatively small because the click data collection and users’
judgments are labor intensive. The evaluation measure is
MAP (mean average precision) which is widely used inranking problems.

5. 2 Results and Discussions
In the real data set, the queries in the last three days are
regarded as repeated IQs. The first seven-day
click-through data is divided into two parts (odd-day andeven-day) as semi-new informational searches. One is forsetting up the QCW user profile and the other is for
re-ranking search results based on the learned user
profile, and then the two parts are exchanged to run theevaluation once again. Here, we set M to be 5 andhf ⋅ | U | to be 20.
In Figure 3 and Table 1, we summarize the performanceof the proposed four re-rank strategies according todifferent hierarchical semantic measures. “MAP
difference” means the difference value between our
strategy and the baseline and “MAP%” represents the
improvement percentage of our strategy over the baseline.

日本データベース学会論文誌 Vol.8, No.1
2009 年 6 月

一般論文

DBSJ Journal, Vol.8, No.1
June 2009

0.18
0.13
0.08

C
1
C
2

Repeated IQ
MAP difference

MAP difference

Semi-new IQ

0.2
0.18
0.16
0.14
0.12
0.1
0.08

C
1
C
2

Figure 3 The MAP differences between our strategies and baseline
Semi-new IQ(%)
Measure Strategy 1
C1
24.92
C2
25.50

Table 1 The MAP improvement percentage of our strategies over baseline
Repeated IQ(%)
Strategy 2 Strategy 3 Strategy 4 Strategy 1 Strategy 2 Strategy 3
25.71
27.13
34.35
55.95
57.72
61.92
28.78
26.64
34.88
56.93
66.71
61.92

The experimental results show that the proposeduser-context aware re-rank strategies are more effective
than the baseline. “Strategy 1”, representing the generalidea of most existing personalized re-ranking schemes, isinferior to other three strategies. Among the proposedfour re-rank strategies, the “Strategy 4” broadly shows thebest performance. The “Strategy 2” with selective
utilization of user profiles, averagely produces better
results than the “Strategy 1” and “Strategy 3”. In Figure 3
and Table 1 the improvement of repeated IQs in is more
obvious than those of semi-new IQs. The larger
improvement of repeated IQs shows that our re-rank
strategies can effectively retrieve the Web pages
previously clicked by users since these queries have been
submitted before and user’s click behavior has been storedin our QCW.
Moreover, in Figure 3 and in Table 1 we observed thatthe similarity measures using nonlinear transformation
function (i.e., C2 shown in orange columns) generally
produce better performance that the similarity measuresusing linear transformation (i.e., C1 shown in blue
columns). In a word, “Strategy 4” with C2 produces thelargest improvement, e.g., its improvements over baseline
are 34.88% and 75% for semi-new IQs and repeated IQs
respectively.
From the results, we can say that re-ranking of search
results through semantic based personalization actually
can enhance the general search. We also confirm that
there are two critical factors: (1) the query-to-query
similarity which captures the long term search interestsof a user (query dependent), and (2) the most recent
search interest which reflects the short term searchbehavior of a user (time dependent). The two factors
indicate that both short-term and long-term memories
contribute to the improvement.

6. Related WorkIn this section we give a brief overview of some related
works in the literature of personalized search. There are
two kinds of context information we can use to model
search experience and capture user search histories. One
is short-term context, which emphasizes that the most

Strategy 4
72.16
75.00

recent search is most directly close to the user’s current
information need [15], [25], [26]. Successive searches in asession usually have the same information need.
Detecting a session boundary, however, is a difficult task.
The other is long-term context, which generally assumes
that users will hold their interests over a relatively longtime. It means that any search in the past may have someeffect on the current search [4], [14], [18], [30]. Thesestudies commonly used all available contexts as a whole toimprove the search result quality and ranking.
Preliminary discussion on this problem in [29] is in thecontext of only exploiting long-term search history ofusers. In addition, several researchers have usedtaxonomic hierarchy (a simple directory based ontology) isused to represent user’s interests in the Web search [4],[10], [16], [18], [20], [24]. However, very few have taken
into consideration the hierarchical structure of thedirectory-based ontology when calculating similarity
values between current search of a user and her searchhistory. Chirita et al. [4] using hierarchical semantic
measure, however, required users to manually selecttopics they are interested in. A unique characteristic of
our STAR framework is the development of a selective useof personalized search history and a combination of longterm and short term user search histories in rank
optimization of personalized search.

7. Conclusions
We presented a STAR framework for selective utilizationof user search behaviors for personalized learning andre-ranking. We designed a novel user search profile called
query context window (QCW) to record the searchbehavior of a user. We developed a query-to-query
similarity model and the fading memory based weightfunction. We showed how our STAR framework carefully
chose and weighed the relevant click records as usefuluser context given an input query and how we appliedhierarchical semantic similarity measures in our re-rank
strategies. The experimental results show that our STARapproach to personalized search and re-ranking approachcan effectively learn user-specific query-dependent
personalization preference and significantly improve the

日本データベース学会論文誌 Vol.8, No.1
2009 年 6 月

一般論文
accuracy of personalized search over the most existing
personalized re-rankings. Our ongoing research includes
designing an effective updating policy for user profiles,
and more effective rank aggregation methods for further
optimization of personalized search.

[References][1] M. S. Aktas, M. A. Nacar, and F. Menczer.
Personalizing PageRank based on domain profiles. In
WEBKDD, 83–90, 2004.
[2] D. Beeferman and A. L. Berger. Agglomerative
clustering of a search engine query log. In KDD, 407–416,
2000.
[3] P.-A. Chirita, C. S. Firan, and W. Nejdl. Personalized
query expansion for the web. In SIGIR, 7–14, 2007.
[4] P. A. Chirita, W. Nejdl, R. Paiu, and C. Kohlsch¨utter.
Using ODP metadata to personalize search. In SIGIR,
178–185, 2005.
[5] Z. Dou, R. Song, and J.-R. Wen. A large-scaleevaluation and analysis of personalized search strategies.
In WWW, 581–590, 2007.
[6] L. Fitzpatrick and M. Dent. Automatic feedback using
past queries: Social searching? In SIGIR, 306–313, 1997.
[7] N. S. Glance. Community search assistant. In IUI,
91–96, 2001.
[8] T. H. Haveliwala. Topic-sensitive pagerank: A
context-sensitive ranking algorithm for web search. IEEE
Trans. Knowl. Data Eng., 15(4):784–796, 2003.
[9] G. Jeh and J. Widom. Scaling personalized web search.
In WWW, 271–279, 2003.
[10] H. R. Kim and P. K. Chan. Learning implicit userinterest hierarchy for context in personalization. In IUI,
101–108, 2003.
[11] Y. Labrou and T. W. Finin. Yahoo! As an ontology:
Using Yahoo! categories to describe documents. In CIKM,
180–187, 1999.
[12] L. Li, Z. Yang, B. Wang, and M. Kitsuregawa.
Dynamic adaptation strategies for long-term andshort-term user profile to personalize search. In
APWeb/WAIM, 228–240, 2007.
[13] Y. Li, Z. Bandar, and D. McLean. An approach formeasuring semantic similarity between words using
multiple information sources. IEEE Trans. Knowl. Data
Eng., 15(4):871–882, 2003.
[14] F. Liu, C. T. Yu, and W. Meng. Personalized web
search for improving retrieval effectiveness. IEEE Trans.
Knowl. Data Eng., 16(1):28–40, 2004.
[15] Y. Lv, L. Sun, J. Zhang, J.-Y. Nie, W. Chen, and W.
Zhang. An iterative implicit feedback approach topersonalized search. In ACL, 585–592, 2006.
[16] N. Nanas, V. S. Uren, and A. N. D. Roeck. Building
and applying a concept hierarchy representation of a user
profile. In SIGIR, 198–204, 2003.
[17] L. Page, S. Brin, R. Motwani, and T. Winograd. The
pagerank citation ranking: Bringing order to the web.
Technical report, Stanford Digital Library Technologies
Project, 1998.
[18] A. Pretschner and S. Gauch. Ontology based
personalized search. In ICTAI, 391–398, 1999.
[19] F. Qiu and J. Cho. Automatic identification of userinterest for personalized search. In WWW, 727–736, 2006.

DBSJ Journal, Vol.8, No.1
June 2009[20] H. rae Kim and P. K. Chan. Personalized ranking ofsearch results with learned user interest hierarchies frombookmarks. In WEBKDD, 32–43, 2005.
[21] V. V. Raghavan and H. Sever. On the reuse of past
optimal queries. In SIGIR, 344–350, 1995.
[22] M. Richardson and P. Domingos. The intelligent
surfer: Probabilistic combination of link and content
information in pagerank. In NIPS, 1441–1448, 2001.
[23] D. E. Rose and D. Levinson. Understanding user
goals in web search. In WWW, 13–19, 2004.
[24] V. Schickel-Zuber and B. Faltings. Inferring user’s
preferences using ontologies. In AAAI, 1413–1418, 2006.
[25] X. Shen, B. Tan, and C. Zhai. Context-sensitive
information retrieval using implicit feedback. In SIGIR,
43–50, 2005.
[26] X. Shen, B. Tan, and C. Zhai. Implicit user modelingfor personalized search. In CIKM, 824–831, 2005.
[27] M. Speretta and S. Gauch. Personalized search basedon user search histories. In WI, 622–628, 2005.
[28] K. Sugiyama, K. Hatano, and M. Yoshikawa.
Adaptive web search based on user profile constructedwithout any effort from users. In WWW, 675–684, 2004.
[29] B. Tan, X. Shen, and C. Zhai. Mining long-term
search history to improve search accuracy. In KDD,
718–723, 2006.
[30] J. Teevan, S. T. Dumais, and E. Horvitz.
Personalizing search via automated analysis of interests
and activities. In SIGIR, 449–456, 2005.
[31] J.-R.Wen, J.-Y. Nie, and H. Zhang. Query clustering
using user logs. ACM Trans. Inf. Syst., 20(1):59–81, 2002.
[32] J. Xu and W. B. Croft. Query expansion using local
and global document analysis. In SIGIR, 4–11, 1996.
[33] J. Zobel and A.Moffat. Exploring the similarity space.
SIGIR Forum, 32(1):18–34, 1998.

Lin LI
Ph.D student of Graduate School of Information Scienceand Technology, the University of Tokyo. She received theMaster degree in Wuhan University of Technology, China.
Her
research
interests
includeWebmining,personalization and recommendation.

Zhenglu YANG

Research associate of Institute of Industrial Science, theUniversity of Tokyo. He received Ph.D degree in the
University of Tokyo in 2008. His research interests
include sequence mining and data mining.

Masaru KITSUREGAWA
Professor and the director of center for information fusion
at Institute of Industrial Science, the University of Tokyo.
He received the Ph.D degree in information engineering in
1983 from the University of Tokyo. His research interests
include parallel processing and database engineering. He
is a member of steering committee of IEEE ICDE, PAKDD
and WAIM, and has been a trustee of the VLDB
Endowment. He was the chair of data engineering special
interest group of Institute of Electronic, Information,
Communication, Engineering, Japan, the chair of ACM
SIGMOD Japan, Chapter. He is currently a trustee of
DBSJ.

日本データベース学会論文誌 Vol.8, No.1
2009 年 6 月