Ranking Strategies for Navigation Based Query Formulation.
Navigating through a hypermedia retrieval system bears the problem of selecting an item from a large number of options available to continue the trajectory. Ranking these options according to some criterion is a method to ease the task of navigation. A number of ranking strategies have already been proposed. This paper presents a formalization of the concept of ranking, and of the aforementioned strategies. Furthermore we propose two strategies allowing a personalized approach to ranking.
Introduction
In some ways, the introduction of mass storage devices like CD-ROM has been a mixed blessing.
True, we can offer large amounts of information, be it sound, video or text. However, the task of
finding the right information has become increasingly difficult. Although indexing the information
somewhat reduces the complexity, the user may not have a clear overview of the indices which are
resident in the index. Such insights can only be achieved by long-time use of an index. Therefore
novice searchers need a large amount of support in order to make full use of the index. At each
item in the index space, numerous links to related items can be traveled. This amount of possible
roads to travel may cause the user to diverge from the original train of thought unintentionally. In
order to keep the user on the right track, it could be necessary to introduce an ordering between
the different trajectories which are available. The first approach would be to present the options
available in a manner which does not take the previous decisions into account. An example would
be that the current user has a strong preference for links which lead to textual information. Then,
we could imagine that the supporting system creates a list of options where the links to textual
information are mentioned first, or where links to non-textual information are not mentioned.
An entirely different approach would be that the previous steps on the trajectory are examined and
used to order the different options for continuing the trajectory. So we could have the supporting
system create a window which mentions something like "Based on previous decisions we strongly
suggest option X for continuing the search." The basis for the ordering is that, should the user
select an option which occurs high in the ranking, he or she will move towards an index item which
is relevant to the information need. This relevance is derived from the actions which have been
performed on the index items which have been presented to the user so far.
A number of ranking strategies are discussed. However, these do not take into take into account
the current fields of interest which a searcher exhibits during the search session. In order to cater
for adaptive ranking methods, we propose two strategies which analyze the searcher's trajectory.
The results of this analysis can be used to rank the different trajectories.
There are numerous ways in which a query can be constructed interactively. For instance a user
may construct an SQL query in this manner. In this paper we will adapt a hypermedia-based
approach called Query by Navigation. The network in which this query construction process takes
place is introduced in section 2. Within this network the behavior of the searcher is discussed
in section 3. In section 4 first an overview is given of various methods of ranking a node's
neighbors. Following this, two new methods which take the behaviour of the searcher during the
current session into account are introduced in section 5. The effect of one of these two strategies is
demonstrated in section 6. Finally, section 7 offers a critical review of the various aspects presented
in this paper.
based Information Retrieval
These days a large portion of information retrieval is based on hypermedia. This section treats
our view on this current trend.
2.1 Two-level architecture
The tool for disclosing a set of documents is a hypermedia-based information retrieval system.
The frame of reference in this paper is a two-level hypermedia architecture [4]. This describes
how a hypermedia can be formed by creating two levels, the document level or hyperbase, and
the index level or hyperindex. Documents can be found in the document level, which is the hypertext
representation of a set of documents O. The content of a document d is described by
its characterization -(d). The second level, the hyperindex level, is a hypertext representation of
the document characterizations. Formally the hyperindex is a tuple hD; Li. The first component
is the set of characterization items or descriptors, the second component is the set of links between
descriptors. Each descriptor in the hyperindex is of a certain medium taken from the set
\Phi text; sound; video
\Psi . Although in many cases a descriptor would be of type text, it is not
inconceivable that descriptors of type video occur. The reason for this is that the hyperbase essentially
is a hypermedia. So if we have a document which is, say a movie, then this document could
be characterized by its title, its cast, its director etcetera. Alternatively we could characterize this
movie by sampling a few stills, and hence introduce descriptors of type video.
2.2 Hyper-index construction
A main feature of hypertext is the link which connects elements of the hypertext on the basis of
some relation between the connected elements. A source for discussion in hypertext research is
the nature of this link. One topic is whether links should be unidirectional or bidirectional. We
advocate a bidirectional nature of a link. The main reason for this is that in order to allow query
by navigation, it should be possible to reach any descriptor irrespective of the starting-point. So
the demand is that if there is a link from d to e, then there should also be a link from e to d.
Following Frei & Stieger (see [5]), a link is a tuple
where
the type of the link
Hyperbase
document
descriptor
descriptor
descriptor
Hyperindex
beam down beam up

Figure

1: Stratified hypermedia architecture
the source of the link
the destination of the link
the activation count of the link
the time of creation of the link
The time axis \Theta is discrete and totally ordered, see e.g. [12]. So if we have one link - 1 , created at
time t, and another link - 2 created at time t 0 , it is possible to decide which of these two links has
been created first if t 6= t 0 . The links in the hyperindex can be partitioned into a set of static links
and a set of dynamic links. The static links have been derived through characterization. Each
user shares these links with other users. Dynamic links are private for each user. Therefore we
propose that the static links have all been created at the same time t 0 . Each time a dynamic link
is created the time is incremented to the next element.
The type of the link determines the relation between source and destination. For instance these
two descriptors could be synonyms. Another type for a link could be the inferred type. Such a
link between two descriptors means that the link is not due to the characterization process. In
stead, it has been created as a consequence of the search actions of a searcher. For more details,
see [2]. For a link - the source is written as s(-), the destination as d(-), and the activation
count as c(-). Each time a link - is traveled, the activation count - c is incremented by 1. As an
additional component we could have the date on which it was created, or the date when it was
last activated. Irrespective of a link's type, links are not transitive and irreflexive. In order to
reduce the cognitive load on the searcher, we imagine that at most one link exists between any
two descriptors. The reason for this is that it may be very confusing for the searcher if descriptors
d and e are connected with a link of type T and another link of type T 0 . This would suggest the
existence of two different relations between d and e.
The distance between two descriptors d and e, dist(d; e) is defined as the minimum number of links
which have to be traveled in order to reach e from d. Because not all links are symmetric, it is
not unlikely that for most pairs of descriptors dist(d; e) 6= dist(e; d).
A conceptual model for the hyperindex is shown in Figure 2. This conceptual model is drawn according
to PSM[9]. Circles represent object types, which can play roles (represented by rectangles)
in fact types. In this case we have only one object, Descriptors. This object can play two roles,
is-source-of and going-to. The relation created by these two roles is called Link. Without going
into details, the bidirectional nature of the link is enforced with the equality constraint. This is
achieved by allowing only populations of fact type Link such that if his-source-of:x; going-to:yi is
a member of the population, then his-source-of:y; going-to:xi is also a member of the population.
Because there is no link from any descriptor to itself we need a constraint which excludes reflexive
populations of the Link fact type. This is done with a so-called Lisa-D constraint (see e.g. [8]):
NO Descriptor is-source-of Link going-to THAT Descriptor
Descr
Type
Link
Link-Type
is-source-of going-to has-inverse
is-inverse-of
has-type is-type-of
Count
Activation
Inverse
Medium-Type

Figure

2: A conceptual model for the hyperindex
3 Query by Navigation
As a means of constructing a query for the retrieval system, Query by Navigation is used. With this
formalism a user is allowed to meander through a hypertext presentation of an index. Descriptors
which are thought to be representative of the Information Need can be marked as such. There is
no need for the searcher to navigate the hyperindex with the underlying intention of constructing
a query. The sequence of search actions (called a search path) are analyzed and an assumption
is made concerning the interests of the searcher. Based on this assumption the search process
is supported by trying to guide the searcher to the index entry which is most likely to be the
representation of the information need. This section discusses the formalism.
Navigation
Verbalisation
Rephrasing

Figure

3: Search process
3.1 The Search Process
In

Figure

3 we have shown the components of the search process. Starting from an initial query,
the search follows up on this by a process of navigation through the hypermedia. After a number
of navigation actions, the searcher might ask for a verbalization of the navigation process, after
which the original query may be rephrased, etcetera. After a number of iterations, the query is
submitted for evaluation.
3.2 Search Paths
In order to let the user construct a description of the information need we allow this user to
navigate through the hyperindex. The sequence of search decisions taken during this navigation is
called a search path. A search path p of k search actions can be written as where the
a i 's are search actions. In every focus the user can execute a search action which manipulates a
number of options. These options are all the descriptors which either refine or broaden the current
focus '.
The set of options in a focus ' is defined as
Definition 3.1
\PsiAs a different approach we could have as an option also a set of documents which, given the
sequence of search actions thus far, could be relevant to the searcher. Following a link to such a
document would mean that a beam down is performed. We do not concern ourselves here with
the question how these documents are determined relevant. The occurrence of documents among
the set of options is merely something which we wish to incorporate in our ranking strategies.
3.3 Search actions
In order to describe the behavior of the searcher in the hyperindex we consider four types of
actions:
1. mark the focus or one of the options as being relevant to the information need (this style of
searching is called berry picking; see e.g. [1]). This is denoted as ?ff.
2. shift the focus to one of the options of the current focus. This is denoted as ! ff.
3. discard an option as not worthy of further pursuit. The denotation for this action is :ff.
Each search action has a focus, i.e. the descriptor where that action is performed, and a subject,
i.e. the descriptor which is manipulated with the search action. The focus is never part of the set
of options, whereas the subject is either the focus or one of the options.
An example search path is shown in Figure 4. We see that some descriptors have been marked as
relevant, whereas some have been marked as not relevant. Depending on the level of experience
of the searcher, some of these designations may contradict each other.531non relevant:
relevant:

Figure

4: Example search path
Definition 3.2
Given a search path we say that descriptor ff has been visited when either one
of the following events has occurred on p:
Ranking
2.
3.
1.
relevant:
non relevant:
2.
1.
Ranking

Figure

5: Search support
1. there is a j such that a j =! ff
2. there is a j such that a
3. there is a j such that a a simplification of a search path we view a sequence of traveled links and a set of marked
descriptors. If a sequence of links - has been traveled, the demand is that we only travel
links originating from the descriptor we have just reached by the previous transition.
After the search process has been terminated the searcher could ask the retrieval system which set
of documents satisfies the constructed query. The query which will be submitted for evaluation
consists of the marked descriptors:
The set of marked descriptors Mark after a sequence of links - has been traveled is a subset
of the set of all visited descriptors.
As a second reflection of the interest of the searcher we have the set of descriptors which has been
rejected. This set is called NMark. Note that due to the fact that contradictions are allowed, Mark
and NMark may have a non-empty intersection.
Earlier in this section we introduced the notion of distance between descriptors. The distance
between a descriptor d and a search path p is defined as the distance between the current focus
of p and d. This means that the distance between d and a search path does not change when for
instance an option is rejected. The distance can only change when an option is selected as the
new focus. When the searcher moves consistently in a certain direction, some descriptors move
constantly closer to the search path. If the current focus of search path p is called f , then
Definition 3.3
The set towards(p; ! e) is defined as
\PsiAt any point on the search path, the searcher may ask for support. If we focus on support in the
form of ranking, a search path like the one in Figure 5 might ensue.
3.4 The number of search paths
In this section we consider the number of possible search paths in a given hyperindex. If this
number of search paths is relatively low, then the danger of a searcher getting lost in hyperspace
is small. In contrast, if this number is relatively high then a lot of effort will have to be put into
preventing a searcher losing track of the original train of thought. First we consider the situation
where in each descriptor it is only allowed to go to one of the options. Clearly problems arise if
we are looking for paths of length l, when only paths of length k ! l can be constructed. In this
case, the number of search paths of length l starting in descriptor d can be expressed as
e2Opt(d)
If we wish to look for search paths of length l ? 0, and there are no options to which the focus
can be shifted, then no such paths can be constructed. In the case where we look for search paths
of length l = 0, then there is only one such path i.e. remaining in d. In order to find all search
paths of length l, we consider each descriptor in turn:
d2D
nsp(d; l) (2)
We express the number of search paths which can be constructed in the hyperindex as follows:
If no cycles occur in the hyperindex, only search paths of finite length can be constructed. In most
cases however the possibility of constructing a cyclic search path exists. This raises the prospect
of an infinite number of search paths. If we examine the hyperindex of Figure 6a, formula 3 gives
a total of 4 search paths: 3 of length 1 (going from d to e, from d to f , and from e to f) and 1 of
length 2 (going from d to e, followed by going from e to f ). There are no search paths of length
3 or more. For the hyperindex of Figure 6b problems arise. the graph of Because this hyperindex
has a cycle, in theory search paths of infinite length can be constructed.
f
e
d
f
e
d
a b

Figure

A more complex situation occurs when in each descriptor it is allowed to mark or reject this
descriptor or any of its options. The complexity arises because in theory it is allowed to perform
an infinite number of mark or reject actions. In order to tackle this problem, if we are in descriptor
d and wish to construct a search path of length l, we can do first do k ! l stationary search actions.
This is then followed by a transition to one of d's options, and from there we construct a search
path of length l transition counts as one search action).
First we examine the case where only the current focus may be marked or rejected. There are
then three actions which can be performed at any point on the search path.
l
e2Opt(d)
If we can not only reject or affirm the focus, but also the options, we have a choice of rejecting or
affirming one of the 1 (the focus and its options) descriptors which can be accessed in
the current focus. This makes for a choice of 2(1 actions.
l
e2Opt(d)
Admittedly, among these search paths there are a lot which, although quite legal, are very unlikely
to be constructed. For instance, performing a large number of marking operations on the same
descriptor will most likely never occur in practice.
4 Ranking of options
In this section we describe how the options in a focus can be ranked. With this we mean that
each option is assigned a measure, telling the user how important that option is with respect
to a certain ranking strategy. Ranking of options is important in order to help the searcher in
choosing options. This particularly becomes necessary when the number of options becomes large.
In our view, the user should have ultimate control over whether ranking should be performed or
not. Also, the strategy which has been used to perform a ranking should be determined by the
searcher. Another topic which should be considered is the time it takes to perform a ranking.
Under no circumstance should a user have to wait for the ranking to be calculated.
4.1 Basic definitions
A ranking of a set of descriptors
\Psi is defined as
When an option is assigned the number 1 we say that this option has a high rank. An option with
a high rank has a high relevance to the information need. On the other hand, when an option is
assigned the number k the option has a low rank. Such an option is then said to be less relevant to
the information need. Each option is assigned only one rank. However it is possible that a rank is
assigned more than once. This could happen when the criterion used for ranking is insufficient to
distinguish between a set of options. For instance, both option could be assigned
rank 4. This would result in a partial ranking. A ranking is often bijective, i.e. ae describes a
permutation of \Delta. We assume that a ranking does not allow gaps, e.g. a ranking which assigns
rank 1 and rank 3 but not rank 2 is illegal.
Definition 4.1
If ae(\Delta) is the ranking of a set of descriptors, then the rank partition ae [i] is the set of
descriptors which are assigned rank i. 2
Because each descriptor is assigned a rank, the union of all rank partitions should result in the set
of descriptors which have been ranked.
Lemma 4.1
ae
Suppose we have for a set of options \Delta two different rankings ae 1 (\Delta) and ae 2 (\Delta). An interesting
study would be to determine the similarity between these two rankings. As a basis for this
similarity we look at the number of times that the two strategies render the same rank for the
same descriptor. For instance, if two strategies both assign rank 2 to option !, then we have reason
to believe that some similarity exists between the two rankings. In contrast, when two strategies
assign different ranks for all options, then we may conclude that no similarity exists between
the rankings. Because a high ranking indicates an option which is important to the searcher, it
is necessary to attach more importance to agreement between high rankings than to agreement
between low rankings. If we have k ranks, each with a weight w, where w
Definition 4.2
The similarity ffi between two rankings ae 1 and ae 2 of a set of descriptors \Delta is given by
w iThe similarity between two rankings is minimal (i.e. ffi(ae 1 each option is assigned a different
rank by both rankings. A maximal similarity (i.e. occurs when both rankings
decide on the same rank for each option. Similarity between rankings has a close resemblance to
the concept of Hamming distance (see e.g. [7]).
A necessary condition for a maximal similarity is that both rankings have the same cardinality
for each rank partition.
Lemma 4.2 ffi(ae 1
In order to illustrate the concept of similarity between rankings we next present an example.
Example 4.1
Suppose we have a set of options
\Psi and three rankings of this set, as summarized
by the following table:
a b c
The similarity between ae 1 and ae 2 is w 2 , since both agree only on the ranking of option b.
Because rankings ae 1 and ae 3 both assign the same rankings to b and c their similarity is
. Finally, the similarity between ae 2 and ae 3 is w 2 . 2
4.2 Ranking strategies
In [13] an overview was given of various possibilities for ranking the options from which a searcher
may choose. These are summarized in this section.
4.2.1 Overview of existing ranking strategies
Given a set of options, the following strategies may be utilized to achieve a ranking of these
options.
random: the options are ranked in a random way. For convenience, we adopt the policy that the
ranking is a permutation of the options.
frequency: based on previous access by other users, each option is assigned a rank. Since it is
quite possible that some links have been equally frequented, the ranking is not always a
permutation of the options.
time stamp: if a link to an option has been created recently, it will be assigned a higher ranking
than 'older' ones. Because static links have been created at the same time the ranking is not
always a permutation.
medium: links leading to non-textual information are assigned a higher ranking. Because it is
quite possible that multiple options are of medium m, in most cases ranking according to
this strategy will result in a partial order.
knowledge gain: rank the options in such a way that choosing a link will maximize a searcher's
gain in knowledge.
Furthermore, the author reported that in many cases users are not interested in previously visited
nodes. This seems to imply that in any ranking, the previously visited node should receive the
lowest ranking. An interesting question therefore is the rank which a strategy assigns to the
previous focus. These strategies need not be applied during the entire session. It could be that
a different strategy is used during different stages of the search process. Moreover, at each stage
it should be possible that more than one strategy is used. For instance, if we have n options, the
first 4 could be ranked according to strategy S 1 , the next 4 could be ranked according to strategy
Also we could choose to partially rank these n options based on strategy S 1 , and
within each partition rank the options based on strategy S 2 .
Notice that the strategies introduced so far (except for the knowledge gain based ranking) work
with a static criterion. Each time the set of options has to be ranked the same set of rules is used.
An other drawback is that for instance with a frequency-based approach, the searcher is made
part of a faceless group of users who are presumed to all have the same interests. Even though
such a collaborative approach has its benefits, we would like to add a personal touch to ranking.
Also with the above strategies, previous actions taken by the searcher, which reflect the current
interest, are not taken into account. We propose to add a sense of dynamic behavior in ranking.
In this paper we introduce two different kinds of ranking:
search target: rank the options based on how much they bring the searcher closer to a descriptor
which is, unknown to the user, highly important.
history based: rank the options based on previously exhibited behavior.
4.2.2 Random ranking
Basically this is not a meaningful ranking. It merely gives the user a feeling that the system is
doing something as a result of his or her actions.
4.2.3 Frequency-based ranking
With this approach, options which have been chosen more often by previous users of the hyperindex
receive a high ranking. This approach can be made more detailed by examining all the links
which lead to an option, and assign a ranking based on the frequency of all these incoming links.
The reason for this is that it gives a clearer view of the importance of an option. In stead of
concentrating on how the option can be reached from the current search path, this new definition
takes into account the fact that the option could be reached via different paths as well. With our
definition of a link, the frequency f(!)of an option ! is given as:
c(-)
4.2.4 Time-based ranking
When ranking occurs according to the time when a link has been created, we assign rank one
to that link which has been created most recently. This is done because such a link can be
considered to have a 'novelty' value to the searcher. The older a link is (with the links which
have been introduced during characterization as the oldest ones), the less value such a link has to
the searcher. Should there be at least one link which has been created after characterization, the
properties of the time axis guarantee that there is exactly one link which is assigned ranking 1.
Lemma 4.3 If ae has been achieved through time-based ranking, then 9 i?1 [ae [i] 6= ?] ) jae
The rank of the previous focus does not receive a low ranking. If we wish to achieve that the
previous focus does get the lowest ranking, we could choose to rank according to the last time a
descriptor has been visited.
4.2.5 Medium based ranking
In most cases, searchers have a clear preference for information of a specific medium. Links to
information of a different medium can, in most cases, be assigned a low rank, or left out of the
ranking. When ranking is done according to the medium of the option, the previous option is not
ranked last automatically.
4.2.6 Knowledge gain-based ranking
Knowledge is viewed as a collection of facts and relations between them. The knowledge graph
([13]) is the graphical representation of this collection. In terms of our hyperindex environment,
each descriptor d is assigned an intrinsic value V d . Beyond that, each descriptor has a value
which reflects the value of its relationship to other nodes (i.e. the options). More precisely, the
links to these nodes receive a value. The combination of these two values is the so-called derived
value v d . In the context of Query by Navigation, the current knowledge of the searcher can be
expressed as the sum of the derived values of all marked descriptors. What then is the rank of
an option? Clearly, the rank of an option which leads to a great increase in knowledge is high,
whereas an option which only slightly increases the searcher's knowledge is very low. One way to
view knowledge is by examining the subset of the documents which have been viewed thus far.
Viewing can be indirect (i.e. by marking a descriptor), or direct, i.e. by reading a document. If
the current knowledge is K ' O, then the gain of knowledge fl offered by choosing option e is
expressed as
Definition 4.3
When we use this definition for ranking options, then an option which characterizes a large number
of previously unread documents will get a high ranking. On the other hand, since the previous
focus is already part of the knowledge this option will have a very low knowledge gain value. Hence
the previous focus gets a very low rank. Should we have an option which is a document, then the
value fl is at least 0 and at most 1. The current knowledge does not make use of the fact whether
a read document has been judged relevant or not relevant. In order to incorporate these relevancy
judgements, we present a partition K
Definition 4.4
The positive knowledge K + is the set of documents which has been marked as relevant:
d2Mark
Definition 4.5
The negative knowledge K \Gamma is the set of documents which has been marked as not relevant:
d2NMark
Definition 4.6
The undecided knowledge K 0 is the set of documents which has not yet been labeled as either
relevant or not relevant. 2
An option which shares a large number of documents with the negative knowledge is not a very
interesting one. It's rank is therefore very low. However an option which shares no documents
with K \Gamma is a very interesting one. So an option which shares a large number of documents with
the positive knowledge is hampered by sharing a large number of documents with the negative
knowledge. This leads us to the following definition for the total knowledge gain value
Definition 4.7
Note that it is quite possible for an option to have a negative knowledge gain.
This measure of knowledge gained only looks one step ahead. Since it is not inconceivable that
an option e offers no gain in knowledge, but that one of e's options in turn offers a wealth of
information, a more advanced measure would look multiple steps ahead. This measure would also
take into account the effort needed (viz. the number of steps) to reach a descriptor. This increase
in knowledge is based on how large a portion of the hyperindex can be reached from a descriptor.
If an option discloses a large part of the hyperindex, hitherto unexplored, then that option will
have a high ranking. Options which do not have any neighbors will receive a low rank.
When we want to extend definition 4.3 to cater for descriptors which lie beyond an option, we need
to define a 'sphere' with radius s. This is the set of descriptors which lie close enough to option e
to be of interest to the searcher. Descriptors which lie close to e are favored over descriptors which
lie on the edge of the sphere. When a descriptor f close to e shares documents with the negative
knowledge, this influences the knowledge gain in a very negative way. If f lies further away from
e, say on the edge of the sphere, then any documents shared with the negative knowledge do not
cause a very negative influence on the knowledge gain. This effect of distance i on the common
positive knowledge is expressed by the coefficient - i ; the effect of distance on the common negative
knowledge is expressed by the coefficient - i .
Definition 4.8
s
f;dist(e;f)=i
Personalized ranking
The ranking strategies of the previous section have in common that they do not reflect the current
interests of the searcher. E.g. the frequency-based ranking works with data gathered during
previous trajectories. This section presents strategies which take the current interest of the searcher
into account.
5.1 Search target based ranking
In principle, each search action has the effect of labeling certain regions of the hyperindex as less
likely to be of interest to the searcher. For instance, suppose we have a hyperindex where the
subject of 'means of transportation' is subdivided into `motorized' and 'non motorized'. Then
when 'motorized' is marked as relevant, it is unlikely the searcher will at some time in the future
mark 'bicycle' as relevant. When a sequence of search actions is regarded, then it could be possible
to hypothesize on the most likely region in which the searcher is interested. When such a search
target can be singled out, then if the searcher continues moving toward this region, the belief in
the hypothesis will increase. When the searcher moves away from the region, the belief in the
hypothesis will decrease. It could even be possible that the hypothesis has to be restated, viz. a
new search target has to be derived. This is the subject of this section, where we introduce the
notion of target probabilities.
5.1.1 Basic definitions
An interesting way to model the effect of a search path S is by assigning a so-called target
probability P (djS) to each descriptor. This probability expresses the probability of a descriptor
being relevant to the information need, given the current search path S. The effect of extending
a search path with an option e is expressed by
Definition 5.1
1where w is the weight which we assign previous decisions. In general, novice searchers are best
served with a low weight, whereas more experienced searchers have greater benefit from a high
weight. These settings are not strict, they are merely defaults. The searcher has the ultimate
control over the actual value of the weight; it can be decreased or increased at will. The continuation
probability C(dje) is the probability of reaching d from e and making d a berry. It is mainly
determined by the network topology.
Every decision causes the target probability of a descriptor to fluctuate. Some decisions will
increase the target probability; these deal mainly with moving towards such a descriptor. Other
decisions will decrease a descriptor's target probability; an example of such a decision is for instance
when the searcher moves away from a descriptor. Suppose we have a descriptor, say f , which has
a marked increase in target probability, i.e. P (f jp) has increased very much by the last action on
p. For example we might have the case that the searcher has moved into a part of the hyperindex
which terminates in a descriptor without branching off in between. Such a hyperindex might be
called a hairy hyperindex (see e.g. [10]). In order to compare a descriptor's increase in target
probability we look at the relative increase in target probability. For instance, if descriptor d's
target probability rises from 0.1 to 0.15, whereas descriptor e's target probability rises from 0.05
to 0.1, then e has the largest relative increase, even though the absolute increase is equal.
Definition 5.2
The search target of search path p is that descriptor f which maximizes
jp)When we are able to point out a certain descriptor as being the search target, the distance function
between descriptors allows us to define a ranking of the options. The rule of thumb for ranking
is hence a question of 'which option offers the shortest route to the search target'. That option
which is closest to the search target therefore receives the highest rank.
Lemma 5.1 For a search path p, the search target is an element of towards(p).
A special property of the target probability is that leaving a descriptor results in a lower target
probability for that descriptor. Hence the previous focus will definitely not be able to become the
search target. Consequently, the previous focus will never be ranked first.
An interesting situation arises if there are n descriptors which lay claim to the title of 'search
target'. In that case we choose that descriptor which lies closest to the current focus. Another
course of action would be to find a descriptor c which serves as a common ancestor of the candidate
search targets, and label this descriptor as the search target.
When a search path S is constructed twice, first with history w, and then with history w 0 , one
would expect that the target probabilities, and hence the radiation coefficients, differ. So, in order
to construct the same search path in both cases, the user would have to select different ranked
options. E.g. if option e in descriptor d is ranked first if history w is used, it might be ranked
second, or third, or anything but first if history w 0 is used. This would lead us to expect that if
different weights on history have been used, different rankings result.
5.2 History based ranking
In the previous section we mentioned that it is possible to decide whether a search path is consis-
tent. The search path p already constructed reflects the interest of the searcher. In order to guide
the searcher in a way which would maintain this exhibited behavior, an interesting strategy for
ranking is one where descriptors are ranked according to the degree in which they uphold consis-
tency. Suppose e is an option of the current focus d. For this option we create an imaginary search
path we presuppose that the searcher will choose e and then mark this descriptor
as a berry. This path is then analyzed in order to determine its inconsistency. If an inconsistency
can be derived, then this option is ranked low. In contrast, when no inconsistency can be derived,
then the option gets a high ranking.
Each option can be expected to change the previously shown interest, either by narrowing it down
or deviating from it. The need exists to assign a measure to each option, expressing how much it
disturbs the behavior.
In order for a search path to be inconsistent, there have to occur two search actions a i and a j
which contradict each other. We distinguish two possibilities for contradictions:
1. action a i marks a descriptor d relevant, while action a j rejects a descriptor e which is similar
to d
2. action a i marks a descriptor d relevant, while action a j marks a descriptor e relevant which
is dissimilar to d
In order to decide whether two descriptors are similar we assume the availability of a similarity
function
Similarity between descriptors can be decided in a number of ways. One such approach is mentioned
in [11]. Furthermore we have two thresholds - s and - d . If the similarity between two
descriptors falls below - d we call these descriptors dissimilar, whereas when the similarity exceeds
- s we call them similar. Finally, the conflicting search actions have to occur within a window h.
This window can be used to support users with different levels of experience. Novice users may
select a small window value, whereas expert searchers may select a large window value.
Definition 5.3
If a search path is rendered inconsistent due to two conflicting search actions a i and a j , then
the level of inconsistency ' of this search path is given by
Suppose a searcher has constructed a search path
At this focus, information on all countries in Western Europe is available, e.g. France,
Belgium. If the searcher asks for a ranking of these countries, since low countries has been
rejected countries like for instance Belgium receive a low ranking. 2
5.2.1 Selecting a low-ranked link
An important question which has to be asked is what happens if the user chooses to disregard the
suggested ranking and instead selects a low-ranked link. If the user then marks the destination
of this link as relevant, the result would be an inconsistent path. One reason for a searcher to
abandon a certain thread of interest is that as a consequence of the information encountered, a
different information need is formed. For instance, if a searcher has shown an interest in subject A,
an interest for subject B can be triggered because certain of the information dealing with subject
A also deals with subject B. After subject B has been sufficiently explored, the searcher might
return to the original train of thought, subject A.
6 Test results
In this section we return to the concept of ranking based on a search target, and test this strategy
for a certain hyperindex. First we introduce a technique to compare two target distributions.
6.1 Basic definitions
Suppose we have constructed two search paths p and q. These search paths give rise to a target
distribution P (djp) and P (djq), respectively. Both p and q consist of n focus shift actions. An
interesting measure with which to compare the target distributions is the entropy (see e.g. [6])
E(P ), defined as
d2D
For an evenly distributed target probability the entropy will be relatively high. In contrast,
for a target distribution with distinguished peaks, i.e. descriptors with a markedly high target
probability, the entropy will remain rather low.
Example 6.1
Suppose we have four descriptors, a, b, c and d. Then the following table shows some example
target probabilities and the associated entropy:
a b c d E(P )444411111.83999Looking at the target probabilities we see that the probability concentrates in descriptor a,
whereas the other descriptors' probability decreases. As a consequence the entropy decreases.For all examples which will follow in this section, we will present graphs which show the entropy
of two search paths.
6.2 Random ranking vs. search target based ranking
In this section we compare choosing an option at random with choosing an option based on
how close this option is to the search target. If options are ranked random and we choose the
first option, the expectation is that in such case the target probability will show no tendency to
concentrate in a select set of descriptors. This would result in a 'flat' distribution and hence a high
entropy. Secondly, we construct a search path by selecting the option with the highest radiation
coefficient. The expectation is that in this case the target probability will become markedly high
for a specific set of descriptors. The graph of Figure 7 shows that the entropy for the search target2.93.13.33.53.7
entropy
step
ranked
random

Figure

7: Entropy for random vs. search target ranking
based ranked path decreases constantly. The search target where options are ranked random shows
an increase in entropy after an initial decrease in entropy.
first
last

Figure

8: The effect of rank selection
6.3 Selecting a low-ranked option
An interesting test would be to compare the entropies of the distribution which would arise if the
following two strategies for selecting a rank are used:
1. select the option with the highest rank
2. select the option with the lowest rank
Selecting the highest ranked descriptor would bring the searcher closer to the search target, whereas
selecting the lowest ranked descriptor would result in moving away from the search target. Although
there is nothing wrong in selecting a low-ranked descriptor every now and then, doing
this persistently would prevent the target distribution from becoming markedly high for a specific
descriptor. The graph of Figure 8 shows the resulting entropy for a search path constructed by
selecting the first ranked option (solid line) and the entropy for the search path constructed by
selecting the last ranked option. As can be seen, selecting the first rank leads to a lower entropy,
i.e. a descriptor with a markedly higher target probability ensues.
6.4 The influence of history
Finally we show the effect of varying the weight which we assign the previous decisions. In this case
we follow the policy of always selecting the highest ranked descriptor. When the previous decisions
become more important, we would expect that moving in a certain direction would inhibit the
target probability from concentrating in a certain set. Consequently, the entropy would decrease
less quickly. From the graph in Figure 9 we see that doubling the weight on previous decisions
causes the entropy to decrease less rapidly.
Conclusions
In this paper we have given a formalization of the concept of ranking. With this formalization, a
number of existing ranking strategies have been formalized. Furthermore we have presented two
strategies for ranking. Both take into account the behavior of the searcher exhibited during the

Figure

9: Entropy decrease for different weights
current search session. The 'static' ranking strategies mentioned, e.g. medium-based ranking are
attractive ones because they are very simple to implement and do not demand a prohibitively
amount of computations. Although the concept of personalized ranking is an attractive one, it
carries the penalty of time-consuming calculations. For instance, finding a search target and
maintaining target probabilities demands a large number of calculations. In fact, it could be
argued that all the work put into computing a search target in order to rank options is akin to
swatting a fly with a sledgehammer. Once a search target is known, the searcher could be brought
there directly. Another approach is that, if the search target remains constant over a sufficient
enough amount of search actions, the search target could be introduced as an additional option.
It should then receive the highest ranking. The level of experience of a searcher again determines
the time over which the search target should remain constant. With new searchers the window
should be large, whereas experienced searchers will benefit from a small window.



--R

The design of browsing and berrypicking techniques for the on-line search inter- face
Augmenting a characterization network with semantical information.
Personalized Search Support for Networked Document Retrieval Using Link Inference.
Stratified Information Disclosure: A Synthesis between Information Retrieval and Hypermedia.
The use of semantic links in hypertext information retrieval.
Entropy and Information Theory.
Coding and information theory.
ter Hofstede
ter Hofstede and
Hairy Search Trees.
A Similarity Measure for Conceptual Graphs.
A General Theory for the Evolution of Application Models.
Helping the user to select a link.
--TR
Coding and information theory (2nd ed.)
Entropy and information theory
Information filtering and information retrieval
Helping the user to select a link
Design and evaluation of algorithms for image retrieval by spatial similarity
The use of semantic links in hypertext information retrieval
Augmenting a characterization network with semantic information
Genetic Algorithms in Search, Optimization and Machine Learning
Information Retrieval
A General Theory for Evolving Application Models
Personalized Search Support for Networked Document Retrieval Using Link Inference

--CTR
Michael Huggett , Joel Lanir, Static reformulation: a user study of static hypertext for query-based reformulation, Proceedings of the 2007 conference on Digital libraries, June 18-23, 2007, Vancouver, BC, Canada
John E. Leide , Andrew Large , Jamshid Beheshti , Martin Brooks , Charles Cole, Visualization schemes for domain novices exploring a topic space: the navigation classification scheme, Information Processing and Management: an International Journal, v.39 n.6, p.923-940, November
hypermedia;search support;query formulation;information retrieval