A retrieval support system by suggesting terms to a user
Hiroyuki SAKAI Kiyonori OHTAKE†† Shigeru MASUYAMA
Department of Knowledge-based Information Engineering, Toyohashi University of Technology
Toyohashi 441-8580, Japan† ATR Spoken Language Translation Research Laboratories
2-2-2 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0288 Japan
Email: sakai@smlab.tutkie.tut.ac.jp, kohtake@slt.atr.co.jp, masuyama@tutkie.tut.ac.jp
Abstract
We propose a support method for information retrieval. This method automatically suggests terms,
which are relevant to a query, to a user, and when the user can not select adequate terms from among thesuggested terms, the method suggests new terms contained in retrieved documents. We implemented an
information retrieval system based on our support method and evaluated it by having users fill out aquestionnaire. From the results of evaluation experiments, we consider that this system is useful for users
who have insufficient knowledge about the fields concerned.
Keywords: information retrieval; human-machine interaction; user support.

1

Introduction

The recent rapid progress in computers and Internet
technology has enabled us to access enormous amounts of
information easily. Accordingly, document retrieval
techniques to obtain necessary information quickly havebecome more and more important. Most information
retrieval systems currently use keywords inputted by users
as queries. However, it is not easy for a user to retrieve theexact information he/she requires. In particular, it isdifficult for the user to represent the information needs by a
few keywords. (It is said that the average number of
keywords
inputted
by
a
user
to
Excite(http://www.excite.com), one of the more popular retrieval
sites on WWW, is 2.35 [1].)Kitani et al. [2] considered that queries vary with respect tothe amount of knowledge about concerned fields andcompared the number of keywords used in a query against
two cases: (1) Users have sufficient knowledge about
concerned fields. (2) Users have insufficient knowledge
about them. Kitani et al. reported that the number of
keywords contained in queries made by users having
sufficient knowledge about concerned fields is greater than
the number of keywords contained in queries made byusers with little knowledge about them [2]. The results
showed that it is not easy for a user to retrieve the exact
information he/she requires, as adequate key-words forrepresenting information needs are hard to find when theuser has insufficient knowledge about concerned fields. If
the number of keywords is insufficient for informing theretrieval system of information needs, one of the following
two cases is conceivable.

[Case1] Documents irrelevant to information needs are
retrieved.
[Case2] A part of the required documents are retrieved.
To cope with this problem, one effective approach is toexpand a query by adding terms relevant to the query when
the keywords inputted by the user are insufficient for
informing the retrieval system of information needs. In theformer case, the user must execute “AND retrieval” forexcluding irrelevant documents, and in the latter case, theuser must execute “OR retrieval” by adding new keywords.
There are a number of related studies on the extraction ofterms to expand a query, see e.g., [3], [4], [5], [6].
We propose a user support method for information retrievalthat suggests to users terms relevant to queries. Our method
has the following three features.
•

The system automatically suggests to users terms
relevant to queries, which are useful for excluding
retrieved documents.

The system extracts terms contained in documents that areassigned high ranks among the retrieval results.
Accordingly, our method can be applied to search engineswith a function for ranking retrieved documents.
•

The user selects adequate terms relevant to
information needs from the suggested terms and thesystem performs retrieval by using the query
expanded by adding the selected terms.

Documents containing many terms that are selected by theuser are assigned high ranks by the system.

•Even if the user can not select adequate terms fromthe suggested terms, our system suggests new terms
contained in retrieved documents without terms thatthe user does not select.

We introduce our method, and evaluate this system byhaving users answer a questionnaire.

2

Method of information retrieval support

2.1

Outline of retrieval processcharacters used are KATAKANA, compound terms,
place names, and organization names are treated as
terms.
[Step 3] The weight value of term w contained in
document s is calculated by the following expression:

W ( w, s ) = tf ( w, s ) × log( S / df ( w))× log( dt ( w) / tf ( w, s )) × log( S − n) (1)tf(w,s): frequency of term w contained in document s,

The outline of the retrieval process by our retrieval support
method is as follows.

df(w): frequency of documents containing term w in set S
of documents assigned high ranks among the retrieval
results,[Step 1] A user inputs a query and the system retrieves
across given documents by using the query. If thesystem retrieves adequate documents, the process ends.
Otherwise, go to Step 2.

dt(w): frequency of term w contained in set S of
documents assigned high ranks among the retrieval
results,[Step 2] The system suggests to the user terms extracted
from the documents assigned high ranks among theretrieval results.
[Step 3] The user selects adequate terms relevant tohis/her information needs from the suggested terms.
[Step 4] The system expands the query by adding theselected terms, and performs retrieval by using the
expanded query.
[Step 5] Return to Step 2.

2.2

Method of term extraction

Our method of term extraction is based on the following
two hypotheses.
[Hypothesis 1] Terms contained many times in documents
relevant to information needs are relevant to the query.
[Hypothesis 2] Useful terms for excluding documents
irrelevant to the user’s information needs from
retrieved documents are dispersed in the documents
set relevant to the user’s information needs.
We consider that even if a term is contained in documents
relevant to the user's information needs, if the term is notdispersed in the documents set relevant to the informationneeds, the term is not useful for excluding documents
irrelevant to the user’s information needs from retrieved
documents. This is because, even if a term not dispersed in
the documents set is important with respect to a document,
the term is irrelevant to the query.
Our method of extracting terms is as follows:[Step 1] The system retrieves documents by using a query
inputted by a user.
[Step 2] The system extracts terms from a set S of
documents assigned high ranks among the retrieval
results. Here, only KATAKANA terms, where alln: rank of document s,
This expression modifies the tf ⋅ idf method to increase
the weight values of the terms appearing many times in the
documents assigned high ranks among the retrieval results
and dispersed in the documents set.
[Step 4] The weight value of term w is maxs∈S W(w,s).
[Step 5] The system compares the frequency of
KATAKANA terms with that of compound terms in
the retrieved document set.
[Step 5.1] When the frequency of KATAKANA terms isgreater than that of compound terms in the retrieved
document set, the weight value of each KATAKANA
term is multiplied with a value calculated by thefollowing expression:
frequency of KATAKANA terms(2)frequency of compound terms[Step 5.2] Otherwise, the weight value of eachcompound term is multiplied with a value calculated by
the following expression:
frequency of compound terms(3)frequency of KATAKANA terms[Step 6] The system suggests to the user the terms ofweight values associated with them in decreasingorder from the largest.

2.3

Query expansion technique

A query inputted by a user is expanded by adding terms
selected by the user from suggested terms. The expanded
query is as follows:Q ∧ (W1 ∨ W2 ∨ W3 ∨ ... ∨ Wn ) ( 4)
Q: query inputted by a user.
W1, W2,…,Wn: terms selected by a user from terms
suggested by the system.

The expanded query can retrieve documents containing atleast a term selected by the user in the documents retrievedby using the query inputted by the user. Among theresulting documents of retrieval by using the expanded
query, documents containing many terms selected by theuser have high ranks assigned by the system when aranking process is applied to the documents. Such a
process is described in the next section. If the user could
select many terms relevant to his/her information needs, asa result of retrieval by using the expanded query,documents containing many terms relevant to theinformation needs are assigned high ranks by the system.

2.4

The ranking process of retrieved documents

The ranking process of the retrieved documents of oursystem is done by calculating the similarity of a document
and the query. We adopt the inner product of a document
vector and a query vector for the calculation. The
document vector and the query vector are made of elementsthat are weight values of the terms defined below.
The query vector: the weight value of a term contained in
the query is 1; otherwise 0.

Q: query inputted by the user,
T1, T2, …, Tm: terms not selected by the user amongterms suggested by the system.

3

Implementation of the system

We implemented an information retrieval system based on
our user support method. This system is implemented on
Linux using JAVA. Our method can be applied to searchengines having a function that ranks retrieved documents.
We use Namazu (http://openlab.ring.gr.jp/namazu/), a
search engine distributed as a free software application.
The system performs retrieval by employing Namazu andranks retrieved documents by using the method shown
before. The system extracts terms from the top 100 ranked
documents where the ranks are assigned by the system toretrieved documents. We employ JUMAN (http://wwwnagao.kuee.kyoto-u.ac.jp/nl-resource/juman.html), version
3.5 as a morphological analyzer. We use NTCIR Testcollection-1 (Constructed from about 330000 abstracts ofpapers) as a set of documents. We show an example ofexecuting the system in Figure 1.

The document vector: the weight value of a term containedin a document is calculated by the following expression:

W ( w, s ) = tf ( w, s) × log( S / df ( w)) (5)tf(w,s): frequency of term w contained in document s,
df(w): frequency of documents containing term w in set S
of the retrieved documents,

2.5

Countermeasure when a user can not selectadequate terms

If a user cannot select adequate terms relevant to his/her
information needs from suggested terms, the system
automatically suggests new terms. The new terms are
extracted from retrieved documents without terms that theuser does not select from the suggested terms. If terms thatthe user can select do not exist, adequate documents for
his/her information needs may not exist in the documentswith high ranks among the retrieval results. Therefore, it
becomes necessary to change the documents from which
the system extracts terms. The system judges that terms
that the user does not select are not relevant to his/her
information needs. If the system extracts terms fromdocuments that containing terms not relevant to theinformation needs, the extracted terms may not be relevant.
Instead, this system adopts documents without terms thatthe user does not select from the suggested terms as
documents from which it will extract new terms. Applying
this method prevents the system from suggesting terms
irrelevant to the user’s information needs. The query is asfollows, which is able to retrieve documents without terms
that the user does not select from the suggested terms.

Q ∧ not (T1 ∨ T2 ∨ T3 ∨ ... ∨ Tm ) (6)Figure 1. An example of terms suggested by the system

4

Experiments for evaluation

We consider that it is inappropriate to evaluate thisretrieval support system by precision or recall. The reason
why is that this system aims to retrieve adequate
documents for a user by interacting several times with theuser. It is therefore not necessary for the user to retrieve
his/her adequate documents by only an initial query
inputted by the user. We illustrate the experiments
evaluating this system in the next section.

4.1

The method of the experiments

We give users topics and evaluate this system by having
the users answer a questionnaire after retrieving documents
relevant to the topics. We also hope that the time consumed

for the retrieval is shortened if this system is in fact useful.
Therefore, we compare the time consumed for retrieval byusing the function of suggesting terms relevant to the topics
with the time consumed for retrieval by not using thisfunction. The experiments for the evaluation are as follows.
[Step 1] The subjects are given the topics and they
perform retrieval using this system.
Half of the subjects are requested to retrieve documents
relevant to the topics by using the function of suggestingterms, and the other half of the subjects are requested toretrieve documents relevant to the topics by not using thefunction.
[Step 2] The subjects select the predetermined number of
documents relevant to the topics.
[Step 3] If the subjects can select the predetermined
number of documents relevant to the topics, theexperiments end.
We perform the evaluation by having the subjects answer aquestionnaire after the retrieval and the time consumed for
retrieval. Four subjects participated in these experiments
for evaluation. We gave each subject six topics of NTCIR
Test-collection-1 (constructed from about 330000 abstractsof papers). The subjects selected 7～10 documents relevant
to each topic by performing retrieval in NTCIR Testcollection-1.

4.2

The results of the experiments

We distributed the questionnaire to the subjects. The
subjects evaluated the system by choosing one of four
items, “1. This is very useful.” “2. This is useful.” “3. This
is of little use.” “4. This is of no use.” As a result, all of thesubjects selected “2. This is useful.” We compared theaverage time taken when the subjects could selectdocuments relevant to the topics by using the function ofsuggesting terms with the average time taken by not using
this function. Figure 2 shows the result.

Figure 2. The average time when the subjects could selectrelevant documents

4.3

Discussion on the experiments

We conclude that the time consumed for retrieval by using
the function of suggesting terms is not different from thetime consumed for retrieval by not using the function. We
gave the subjects topics of NTCIR Test-collection-1 asinformation needs. The information needs were therefore
clearly stated, and it was easy for the subjects to represent
queries. Even if a subject performed retrieval by not using
the function of suggesting terms, he/she could end the taskquickly if he/she could represent the query by using terms
contained in the topics. Therefore, the system may notaffect the time consumed for retrieval. However, eachsubject answered that this system is useful. The reason theygave is that, for example, even if a user performs retrieval
by using a keyword that is inadequate, he/she can exclude
retrieved documents by selecting suggested terms. We
consider that this system is useful for users by thisevaluation.

5

Conclusion

We proposed a user support method for information
retrieval that suggests terms relevant to a query andimplemented an information retrieval system based on ouruser support method. We consider that it is inappropriate toevaluate this retrieval support system by precision or recall.
Therefore, we also evaluate this system by distributing aquestionnaire to subjects.
From the results of thequestionnaire, we consider that this system is useful forusers.

Reference
1

Jansen, B. J., Spink, A., Bateman, J. and Saracevic, T.
Real life information retrieval: A study of user
queries on the web. SIGIR Forum, 1998, 32(1), pp. 5
- 17.

2

Kitani, T., Takaki, T., Kihara, M. and Sekine, M.
Information Retrieval Using a Full-text and Extracted
Keywords. In IPSJ SIG Notes 96-NL-115, 1996, pp.
129 – 134, (in Japanese).

3

Kawano, H. and Hasegawa, T. Data mining
technology for WWW resource retrieval. In IPSJ SIG
Notes 96-DBS-108, 1996, pp. 33 – 40, (in Japanese).

4

Kambayashi, T., Shimizu, S., Sato, S. and Francis, P.
Keyword Extraction for World-Wide Information
Discovery. In IPSJ SIG Notes 97-NL-118, 1997, pp.
79 – 84, (in Japanese).

5

Sunayama, W., Ohsawa, Y. and Yachida, M. A
Search Interface with Supplying Search Keywords byUsing Structure of User Interest. Journal of Artificial
Intelligence, 2000, 15(6), pp. 1117 – 1124, (inJapanese).

6

Miyata, Y., Furuhashi, T. and Uchikawa, Y. Query
Expansion for Information Retrieval Support System
Using Fuzzy Abductive Inference. T.IEE Japan, 1999,
119 - C(5), pp. 632 – 637, (in Japanese).