Discovery and Retrieval of Logical Information Units in Web
Keishi Tajima

Kenji Hatano
Takeshi Matsukura
Katsumi Tanaka

Ryouichi Sano

Department of Computer and Systems Engineering
Kobe University
Nada, Kobe 657-8501, Japan
Tel/Fax: +81 78 803-6234
tajima hatano matukura sano tanaka @db.cs.kobe-u.ac.jp











KEYWORDS: Web, hypertext, query, data unit, structure discovery, information discovery

ABSTRACT

In ordinary search engines for Web pages, the data unit
for query processing is individual pages. Indexes areproduced for each page in accordance with the words
appearing in it. In actual Web data, however, a logicaldocument discussing one topic is often organized into
a set of pages connected via links provided by the pageauthor as “standard navigation routes.” In such a situation, conjunctive queries with multiple keywords may
fail to retrieve an appropriate document if those keywords appear in different pages within that document.
Therefore, a data unit for Web data retrieval should not
be a page but should be a connected subgraph corresponding to one logical document. In this paper, we develop new techniques for discovering and retrieving the
logical information units in Web data. As in some previous researches, we adopt minimal subgraph semantics
for conjunctive queries. In our approach, when given
a conjunctive query, we try to approximate information
units including all the given keywords in the following
three steps: (1) we distinguish standard route links fromthe others, (2) we find minimal subgraphs connected
via those links and including all the keywords, and (3)we compute the score of each subgraph based on thelocality of the keywords within it in order to examine
whether it is really a logical information unit relevantto the query.

1 INTRODUCTION

Web data is a huge hypertext data consisting of a huge
number of Web pages and links connecting them. Links
are used in various ways. Some links are used to provide a way to jump to Web pages at other (or same)
Web sites discussing a related topic. On the other hand,some links are provided by the page author as the suggested navigation routes going through a set of pages
which as a whole compose one complete document. For
example, a document is sometimes organized into a sequence of pages corresponding to its sections. Links
with anchors saying “next” composing such a sequence
are typical examples of the latter kind of links. Similarly, pages describing various information on one topic
are sometimes organized into a hierarchy. Links goingdown within such a hierarchy are also examples of thelatter kind of links. In pages organized in those ways,
links going back to some prior pages along the routes,
e.g. links to the previous page with anchors “back” orlinks to the top page with anchors “top,” are also often
found.
The users can retrieve Web data either by directly accessing Web pages at known URLs, or by navigatingfrom pages to pages via those links. Currently, however, another important way to access Web pages is thecontent-based access via search engines. Search engines provide facilities to list up URLs of pages including given keywords. When a user want to newly findunknown pages discussing a topic of one’s interest, one
can submit a query to search engines by specifying keywords that are likely to appear in pages on that topic.

Permission to make digital or hard copies of all or part of this workfor personal or classroom use is granted without fee provided that
copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first
page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
Proc. of Workshop on Organizaing Wep Space (WOWS’99)
in conjunction with ACM DL’99 Berkeley CA USA, Aug. 199913

 Page contents — this approach analyzes the contents

In ordinary search engines for Web pages, the data units
for retrieval is individual pages. As mentioned above,
however, a complete document discussing one topic isoften organized into a sequence or a hierarchy of pages
connected via “standard route” links. In this way, a logical information unit in Web data is not a page but is aconnected subgraph corresponding to one logical document, and therefore, so should the data unit in Web
query be. If we use individual pages as the data units
in query processing, conjunctive queries with multiple
keywords would fail to retrieve some appropriate document when those keywords happen to appear in different pages of that document.

classification based on the information used for unit discovery

Recently a couple of researches including ours haveproposed frameworks for querying those logical information units in Web [22, 23, 26, 16, 13, 9, 8]. The approaches to discover and retrieve such logical information units are classified in several ways as follows.

 Static approach [22, 23, 26, 13, 8] — this approachstatic approach v.s. dynamic approachstatically divides the Web graph into fixed subgraphs
corresponding to logical documents. When a query isissued, logical information units including all the given
keywords are returned. This approach is a natural consequence of our original observation that there exist in
Web data logical information units intended by page authors. The advantage of this approach is that we can
employ complex analysis for the information unit detection without causing the response latency at query
execution because the analysis can be done in advancein the phase of index creation.
Dynamic approach [16, 9] — this approach dynamically finds a information unit including all the query
keywords each time a query is issued. In this approach,partition of the Web graph into units is variable depending on the given query. In the existing researches,[16] and [9] use minimal subgraphs including all thequery keywords as approximations of information units
matching to the query. Some of such minimal subgraphs, however, may not actually be part of one information unit but may be spanning to multiple documents.
To give priority to subgraphs that are more likely to bepart of a single document, [16] uses a query relaxation
schemes based on the size of the graph and [9] uses
a ranking algorithms. The advantage of dynamic approach is that it can always return “bestresults” asmentioned in [16].

of pages in order to detect logical information units. For
example, in many researches, the term frequencies ofneighboring pages (or subgraphs) are compared, andsimilar neighboring pages (or subgraphs) are merged
into one logical information unit [22, 23, 26]. On theother hand, [13] uses the similarity of tagging patterns
in neighboring pages. Other techniques to capture thesemantics of the documents, such as natural language
processing techniques, may also be effective.
Link structure — another approach is to use information on hypertext structure. For example, graph theoretic properties, such as various kind of connectivity [2,23, 21, 8] or fun-in/fun-out [2, 23, 8] can be clue to detecting strongly related pages. In dynamic approaches[16, 9], the size of subgraphs are used in query relaxation schemes or in answer ranking.
Directory structure — another useful information that
we can find in Web data is directory structure embedded
in URL. It usually reflects the intention of page authors,and is very useful to guess which links are intended tobe the standard routes [21], or which set of pages areintended to be composing a single document [23, 8].
In this paper, we develop new techniques for discovering and retrieving logical information units in Web data.
In this paper, we adopt the dynamic approach, particularly the minimal subgraph approach. The reason of the
choice is, although the static approach is more straightforward solution to the problem “retrieval of logical information units,” it is quite difficult to detect such units
perfectly. In some cases, even the author oneself cannot tell which pages are composing a single independent document. Therefore, minimal subgraph approach
is more practical.
One problem in dynamic approach is the cost to dynamically traverse Web graphs to find minimal subgraphs.
If we examine arbitrary subgraphs, they usually include
many subgraphs that are clearly not part of a single logical document. Searching those subgraphs is wastingtime. We need some method to eliminate those “clearlywrong” cases in some early phase. The cost grows especially when the average of fun-out, the number ofout-going links from a page, is large. Therefore, reducing the number of links to traverse is very effective
to reduce the cost. In this research, we eliminate links
that are not intended by page authors to be the standard
routes, i.e. not part of a single document, by looking at14

directory structure in URLs.

hand, our purpose is to detect a single document written by one author.

In dynamic approach, some query relaxation scheme orsome ranking algorithm is also essential as explained
above. In this research, we use a ranking method basedon the “locality” of query keywords in subgraphs. A locality of a word is the area where the word has its influence. If localities of two words greatly overlap, those
two words must be strongly related in that subgraph,and if they does not overlap at all, those words may beunrelated. Therefore, if the locality of query keywords
in a subgraph greatly overlaps with each other, we rankthat subgraph higher. We examine the locality of words
both across pages and within each page.

There are also many researches on utilizing both content information and link information for retrieval orclustering of hypertext data [5, 27], for ranking Web
pages [12, 19, 4, 3], or for classifying Web pages into
several page roles [24]. Although those approaches incorporate link information in querying or clustering hypertext data, they still use individual nodes as data units
for retrieval, ranking, or classification.
There is a research proposing the detection and the utilization of subtopic structure in large documents [10].
They divide a long text into smaller fragments each ofwhich corresponds to each subtopic, and use both thosefragments and the whole document as the data units incomparison with given queries. The concept of subtopic
structures and the concept of the logical information
units in Web data is very similar. [10], however, deals
not with hypertext but only with sequential texts.

In summary, when given a conjunctive query, we find(approximations of) information units including all the
given keywords in the following three steps: (1) we distinguish route links from the other kind of links, (2)we find minimal subgraphs connected via those links
and including all the keywords, and (3) we compute thescore of each subgraph based on the locality of the keywords in order to examine whether it is really an information unit relevant to the query. We develop techniques for each of these steps, discuss the rationality ofthe semantics of conjunctive queries for Web, and show
our preliminary experimental results.

Our first research on the detection of meaningful subgraphs in hypertext data is [11]. In that research, wehave proposed a method for identifying connected subgraphs discussing one topic in newsgroup articles ormailing list archives, which have hypertext structure induced by “Reference:” or “Reply-to:” header information. We used similarity between neighboring nodes
based on the term frequency. In the workshop where we
presented that paper, Hiroyuki Kawano of Kyoto University suggested that the same idea can also be applied
to Web search. Following that suggestion, we have developed a framework to detect meaningful subgraphs in
Web data and to use those subgraphs as the logical data
unit in the retrieval [22, 26].

The reminder of this paper is organized as follows. Next
section discuss more about related work. Section 3 describes the three steps of the retrieval of logical information units. Then Section 4 discusses various semantics of conjunctive queries on Web data, and the relation
between our method and them. Finally Section 5 is conclusion.
2 RELATER WORK

An early research on the detection of meaningful connected subgraphs in hypertext data is [2, 1]. They identify connected subgraphs consisting of strongly related
nodes based on the graph structure in order to produce
a summary or an overview map of the whole structureof huge hypertext data. On the other hand, this paperand [22, 23, 26, 16, 9] have proposed to use such meaningful subgraphs as the logical data unit for Web data
retrieval.

The idea of using minimal subgraphs including all keywords is, as far as we know, first suggested by Yoshinori Hara of NEC USA. In an informal meeting withus, he suggested it as another solution to the problem
of conjunctive queries in Web retrieval. Later, that idea
was presented in [16] by members of NEC USA, and in[9] by some of us. In [16], query results are progressively produced in the order of the size of the subgraph,
which must also be the order of the relevance of the subgraphs to the query. [9] proposed a method of ranking
subgraphs based on the locality of keywords across thepages, i.e. how query keywords are distributed to pages
in a subgraph. In that framework, subgraphs where[14, 6] also developed a method to extract “communities” of pages, the group of pages that are written by authors having the same interest and are referring to eachother, by examining the link structure. On the other15

multiple query keywords appear together in many pages
is ranked higher than subgraphs where keywords appear
disjointly. It is because those keywords seems morestrongly related to each other in the former case.

In this paper, we revise the ranking method proposedin [9] so that it reflects the size of subgraphs. In addition, we extend the concept of locality. In our new ranking method, we examine not only the locality of words
across pages but also the locality of words within eachpage. If two query keywords appear at positions far
from one another in a very long page, those two keywords may not be related at all. It often happens especially in “link collection” pages. Therefore, we rankthese cases lower than those where the positions of keywords are close to each other.



These are modified version of the assumptions adopted
in [21]. We modified them in two ways. First, weare more conservative here because in this research wewant to exclude only links that are clearly not a routelink. Second, in this research we want to detect routelinks in order to reduce the cost of detection of logicalinformation units. As explained in a later section, in
our current implementation, we incrementally retrieve
pages starting at URLs given by other existing searchengines. We distinguish non-route links in order to reduce the time cost by not retrieving pages linked via
non-route links. Therefore, we have to decide whether
a link can be a route link or not before retrieving its destination page. The heuristics above were simplified sothat they use only URLs of source and destination pagesof links.

In this paper, we also introduce a technique to distinguish links working as browsing routes within a single
document and other kind of links. The technique we use
in this paper is a simplified version of the techniquesdeveloped in [21]. By this technique, we improve theefficiency and accuracy of the automatic information
unit detection. [25] also discussed that all links are notequally useful and that we should use link information
selectively by distinguishing various link types. In thispaper, we use the concept of “route links” introduced in[21] to improve the detection of logical documents inWeb.
3 DISCOVERY OF LOGICAL INFORMATION UNITS

In this section, we explain each steps in the detection oflogical information units.
3.1

page named index.* or a URL ended by /, in thesame directory is never a route link. Otherwise, a link
between pages in a same directory may be a route link.
A link going from a page to a page in an incomparable directory can be a route link only when those two
directories are siblings, i.e. immediate subdirectories inthe same directory.
A link going from a page to a page on a different Web
server may be a route link in some cases [21], e.g. whena logically single Web site is physically divided into
multiple servers such as www.acm.org, www1.acm.
org, and so on. In this research, however, we assume
that a logical information unit never span multiple Web
servers. Therefore, in this research, we assume links
across different Web servers are never route links.

3.2 Extraction of Minimal Subgraphs

Route Links and Non-route Links

Next step is to extract minimal subgraphs including all
The first thing we do for the detection of information
the given query keywords. In our prototype implemenunits in Web data is to distinguish links that are meanttation, we extract them by the following procedure:
to be the standard browsing routes through which allreaders should navigate. We call those links route links.
We distinguish them because we consider a set of pages 1. We transform the query of the form
into a disjunctive query, and subthat is meant to be one logical document is always conmit
toanexisting
searchengine.
Currently,
we arenected by that kind of links.
using goo [7], which is the most popular search engine
In this research, we use directory structure encoded inin Japan.
URLs to distinguish route links. We adopt the following
2. We traverse links one step deeper starting from every
heuristics:
page returned by that query. We traverse only links that
A link going from a page to a page in a subdirectory
are determined as route links by the method explained
may be a route link.
above.
A link going from a page to a page in an upper directory is never a route link.
3. After we have retrieved all pages linked from the pages
A link going from a page to an index page, i.e. ain the queue, we examine if any subgraph includes all









16

  
     the query keywords.

(1)

5. In many cases, there are subgraphs that have exactly
the same set of nodes including the query keywords,
but differs only in nodes with no query keywords. We
exclude those subgraphs but the one with the highest
rank. The method to compute rank is explained in thenext subsection.

(3)

Previous
Formula

0.250

0.167

0.333

0.667

0.400

0.500

0.833

0.450

0.750

1.167

0.650

0.667

1.333

0.700

0.833

Next step is to sort found minimal subgraphs in order ofscores calculated based on the localities of query keywords. In this paper, we propose the following function
to calculate the score of a subgraph :k2^ k3

1.667

0.733

1.333

k3

1.500

0.750

1.000

1.833

0.783

1.500

k1^ k2k2^ k3k1^ k2k3

k1

k2^ k3(4) k1^ k2

k2

k2^ k3k1^ k2

k2

k3

k1

k2

k2^ k3

Ranking Method(6) k1^ k2



(7)


  !#" (')+* -,/. 10$%&')+*  is the number
where 2 is a set of pages in  , and*of query keywords appearing in the page . . is a pa-

(8)

k1

k2

k1^ k2k3

k1

k2^ k3Figure 1: Examples oframeter to adjust the cost value, which will be explainedlater.



Current
Formula(C=3)

k1^ k2^ k3

(2)

(5)

3.3

Current
Formula(C=1)

Minimal Subgraph

4. When we have found enough number of answers, westop the traverse. Otherwise go back to Step 2.

')+*ED  ')+*F ')+* 
')+*(')+*  ,A.4 * DHG * F)I 2

3
(')+* 5,64.   0This function sums up the cost of every page in the subaregraph . Subgraphs with smaller value of.
ranked higher. The cost of each page is
The larger the number of keywords in the page is, thesmaller the cost of that page is.



it. Equality holds only when
for all. Generally, when the average ofisconstant, the larger the variation ofis, the larger
the average of the inverse ofis, and therefore, so is.
The larger is, the stronger the effect of the size ofthe subgraph on
is. On the contrary, the smalleris, the stronger the effect ofis. Particularly, theeffect of the variation of
becomes more significant. When
, subgraphs including a page withno keyword are eliminated even if other pages include
many keywords because the cost of a page with no keyword is infinite.

.

We can also interpret it as consisting of two factors as
below:

  !879: " (')+* -,/.  0
7 $%&where 7 is the number of pages in 2 . From this inter3
pretation, we can see the following properties of   : When the second factor is constant, 3   is proporto 7 , i.e. the size of the subgraph.
3   istionalWhen the size of the subgraph is constant,proportional to the second factor, the average of the in(')+*  ,;.  , which is, very roughly speaking,verse of')+*  .
inversely proportional to the average of3 4  
. 3



.JLK

')+*
')+*  3 4

On the other hand,does not reflect the shape ofthe graph at all. For example, a subgraph consisting of aroot page and its two children and a subgraph consistingof three pages organized into a sequence have the sameof those three pages are equal.
score as long as
The reason of this design decision is that the shape ofthe graphs depend on the organization style of authors,
and we cannot tell which shape is better. For example,
the same document may be organized into one root pageand its many children by some author, and be organized
into a sequence by other author.

')+* 

 Moreover, the following inequality holds::7 $" %<& (')+* -,/.4 0 >=@? 7 : $" %<& (')+* -,A. 1B 0
(')+* >,C.4 isThat is, the average of the inverse of

3 4 for various sub3   with .M in:

Figure 1 shows the values ofgraphs. Here, we show two cases,

greater than or equal to the inverse of the average of173 4.NNO

the second column, andwithin the thirdcolumn. In the fourth column, we also show the scoreof each subgraph computed by the formula proposed in[9]. It was the formula below:

somewhere near the top of that page, and another query
keyword appears near the bottom of that page, those
two keywords must not be related strongly. We want torank such pages low.

3 4! : " (PRQTS-(')+*  G : U 0
7 $%<&
7(In [9], the inverse of the formula above was used, and3subgraphs with larger 4 was ranked higher. In thisTo measure how strongly words in the same page are
related, we use appearance density [15] of those words.
An appearance density of a word at a position is calculated based on the frequency of the word within a “window” around that position. We regard it as reflecting theimportance, or the degree of the influence, of the word
at the position.

comparison, however, we use the inverse of it in order tomake it easier to compare the result of two formulae.) In
the formula proposed in [9], its score does not properlyreflect the size of the graph (e.g. see (3) and (4)). In
our new function, however, the size of the graph is theprimary factor.

To calculate appearance density of words, we need to
select a window function. We consider that a document is a sequence of words, and suppose denotes
the length of the sequence. Window function defines
the weight value from 0 to 1 for each position from 1 toin the sequence. The most simple window function
is a rectangular window function which gives 1 to every
position within a window of some fixed width and gives
0 elsewhere. In this paper, we use Hanning window, Hanning window function centered atfunction.
, is defined by the following formula:V

V

In Figure 1, subgraphs are sorted in order of:
1. the number of pages,')+*  , and')+*  .
3. the variation of
When .NO , the order of the cost is exactly the sameorder. When .M
: , the order of (6) and (7) is reversed.
It is because when . is small, the effect of pages withsmall number of keywords is strong.
3 4 reflects the distribution of the locality of keywords across pages in the subgraph. When keywords
are distributed to many pages, 7 becomes large. When
7 is constant, the more the localities')of+*keywords over is, and therelap, the larger the average number of   is. (See (2) and (3),fore, the smalleror (4), (5),')+*  isand (7) in Figure 1.) When the average of

YW X +Z 
D
W\X +Z  ] ^  : ,)_a`cbed<f g 0 X 
h Z-i [ hkj g ^Kotherwise(1)
where l is the width of a window (a range where a
+Z
non-zero weight is given). WYX  gives its maximum
Z [value 1 at the center of the window, i.e. at  , andZ
it gets smaller as gets far from the center.
mcn +Z  , the appearance density of a word o at a position Z

2. the average of[using Hanning window function, is defined as follows:m n +Z p Fsrq" W DUut vxw n ut 

3.4

(2)

w n +Z  is defined as below:
nw +Z p ] : the word o appears at the position Z
K otherwise
mcn +Z  sums up the weight values of all positions where
the word o occurs. We consider that it expresses theZ
importance the word o has at the position , and that the
c
m
n
+

Z
area where is high is the locality of the word o .
mcn +Z  for os . In the docuFigure 2 shows examples ofment at the top, o occurs twice, and the distance be-constant, subgraphs where keywords are continuously
overlapping in every page is ranked higher than subgraphs which can be divided into two (or more) subgraphs with many keywords and pages between themwith few keywords. (See (5) and (6), or (7) and (8) inFigure 1.)

where

Appearance Density of Words

Next, we examine whether two words appearing in thesame page are really related to each other. Even when
two words appear in the same page, sometimes thesewords are not related at all. For example, suppose there
is a very long “links page” listing many links and brief
explanations for them. If a query keyword appears at

tween them is longer than the width of the window.

18

d(i)
_
d(i)
1.0

t1

0.8

t1

t1

0.6

i

d(i)

t2

r(t1,t2)
0.4

t1

0.2

t1
0

i
Figure 2: Examples ofmcn +Z 

Figure 3: An Example ofm n(y +Z  in that document has two separate part of theform of the window function as shown at the right ofthe document. In the document at the bottom, os occurs
twice, and the distance between them is shorter thanmcn y +Z  in that document is
the width of the window.

i

_
d(i)

shown at the right of the document. In this case, thetwo parts corresponding to two occurrences overlaps,
and the graph is sum of two graphs of the window function.

locality K1

mzn +Z 

In order to measure the importance relative to other positions in that document, we normalize
so that thewithin a document be 1. We define relative
peak ofappearance density
as follows:mcn +Z   os G o ^ locality K2

zm { n +Z 
mc{ n +Z p P3|Emc} n +Zmc n ut
U~ F ~ q
 G
Now we define  o o ^  , the degree of the interrelationof two words os and o ^ , by the formula below:  os G o ^  U~PRD |E~ } P3QTS mc{ n(y +Z  G mz{ n +Z Uq  GFigure 3 shows an example of  o1 o ^  . In that graph,mcn(y +Z  and the normal line repthe dotted line representsm n DT . Then   o1 G o ^  is the value of mcn(y +Z  at the
resentsrightmost peak, which is the highest peak among thosemcn +Z  .
that are within

i

_
d(i)

locality K1
locality K2iFigure 4: Examples of related words and unrelated
words

19



 recall ratio relative to 7j; , i.e. the ratio of the number of correct subgraphs of size less than 7 to the number of correct subgraphs of size less than 5.
for 7 from 1 to 5.

  o1 G o ^ p K

When the localities of two words do not overlap at all as
in the example at the top of Figure 4,. On
the other hand, when the localities of two words greatly
overlap,
has a large value as in the example atthe bottom of Figure 4.

  os G o ^ For Q1, very large percentage of correct answers are
consisting of one page. Therefore, they can be retrievedby a simple page-based conjunctive query. In Web sitesof some companies, however, the word “catalog” does
not appear in each catalog page but appear only in theroot pages of those catalog pages. This kind of pages
are retrieved as subgraphs of size 2 or 3. No subgraphsof size larger than 4 are retrieved.

In Web pages, however, words in a title tag, or the main
heading at the top of a page have their influence all
through the page even if they do not appear in the rest of
the page. To give special treatment to these words, wefor any if is in a title tag or in a main
defineheading of a page. Title tags can easily be detected.
On the other hand, in order to detect the main headings of pages, we use a Perl module HTML::Parse in
HTML-Tree, which is a free software library distributedby libwww-perl [18].

mz{ n +Z 

Z o:

Although the minimal subgraph approach does not significantly improve the recall ratio for Q1, it does not
significantly reduce the precision ratio either. Therefore, when we want to create “complete” list of catalog
pages of PC cards, introducing minimal subgraph queryis meaningful.

3  

   3 4" (  ')+* E,3 nT n %  $   o DG o F ,.4 0$%<&+*  is the set of query keywords appearing in
where *.

Now the formula has three parameters ,  , and . .
')+* Coefficient and  define the weight given toGand  o o ^  . Currently we are testing this formula by
experiment, and finding the best values for ,  , and . .

In order to makereflect the locality of keywords
within pages, we redefine
as below:

Table 2 shows the result of Q2. The homepage of Ryoichi Sano cannot be retrieved by a simple page-based
query because: in the member list page of our research group, theThe evaluation of the real effectiveness of this formula
is a future issue.
3.5Preliminary Experimental Results

 Q1: notebook, card, catalog — whose intention is
We tested the following queries with 2 or 3 keywords:

to collect all the product catalog pages of PC cards fornotebook computers
Q2: “Ryoichi Sano”, “Kobe University”— whose intention is to find the homepage of Ryoichi Sano, who isa student of Kobe University. (Both “Ryoichi Sano” and“Kobe University” are treated as one word in Japanese.)word “Ryoichi Sano” appears but the word “Kobe University” does not,the homepage of Ryoichi Sano is divided into a main
frame and a sub-frame, and in these frames, the word
“Ryoichi Sano” appears but the word “Kobe University” does not, andthere is a separate page describing the profile of Ryoichi Sano, which is linked from the sub-frame of his
homepage, and that page includes the word “Kobe University” but not the word “Ryoichi Sano.”
As a result of it, the homepage of Ryoichi Sano is retrieved by Q2 as a subgraph of size 4 (the member list
page, two frames of homepages, and the profile page).
As far as we see the result of those example queries, theminimal subgraph approach seems useful for the following kinds of queries: the number of returned subgraphs of size 7 , the number of correct subgraphs among the returned,
onestheofratiosizeof7 thenumber of correct ones of size 7 to thereturned ones of size 7 , the ratio of the number of correct subgraphs of size
less than 7 to the number of returned ones of size lessthan 7 , andThe result of Q1 is shown in Table 1. This table shows: recall-oriented queries, i.e. queries where we want

list of relevant pages, and“complete”
queries to retrieve very specific page which must be
somewhere but whose URL is unknown, for example
the homepage of xxx. In this case, if some keywords
which seem very appropriate for query happen to occur
only in neighboring pages, minimal subgraph approach20

Table 1: Precision and Recall Ratios for Q1

7 (the size of subgraphs)

the number of returned answers
the number of correct answers
precision ratio (within each )precision ratio (accumulative)
recall ratio (relative to
)

7jA

7

1
980
682
0.696
0.696
0.959

2
27
17
0.629
0.694
0.983

3
21
12
0.571
0.691
1.000

4

5

0
0
–
0.691
1.000

0
0
–
0.691
1.000

Table 2: Precision and Recall Ratios for Q2

7 (the size of subgraphs)

the number of returned answers
the number of correct answers
precision ratio (within each )precision ratio (accumulative)
recall ratio (relative to
)

7jA

7

1

2

3

4

5

0
0
–
–
0.000

0
0
–
–
0.000

1
0
0.000
0.000
0.000

1
1
1.000
0.500
1.000

0
0
–
0.500
1.000

is very useful.

the keywords are related to each other, and are cooperatively describing the topic of the interest. An example
of and query is a query with keywords “Web” and “visualization”, whose intention is to retrieve pages discussing a topic related to both Web and visualization
techniques, e.g. visualization of Web data, or visualization of some kind of data using Web environments.

4 DISCUSSION

In this section, we discuss the semantics of conjunctive
queries for Web retrieval and the rationality of our approach.
In most search engines, there is only one form of conjunctive queries: a list of keywords in order of importance. Conjunctive queries with multiple keywords ,, and are, however, used in various intentions such
as:

o^

o

o1

of queries are special cases of and queries, where there
is a clear order among keywords from general terms tospecialized terms. An example of of query is a querywith keywords “Workshop”, “SIGWEB”, and “ACM”,
whose intention is to retrieve homepages of workshops
sponsored by SIGWEB of ACM.

 also query: intending to retrieve pages discussing o1 ,o ^ , and also o ,andandalsoquery:intending to retrieve pages discussing “osand o ^ and o  ”, and

There are also combinations of those three kind of conjunctions. In addition, those three kinds of conjunctions
cannot always be distinguished clearly. There are mediums of some two.

of query: where there is a clear order among keywords from general terms to specialized terms, and the
keywords narrow down a topic stepwise in that order,
like “ of of .”o1 o ^ o 

The appropriate criterion for ranking retrieved queryanswers varies depending on the type of queries. In
this research, we use the size of subgraphs and overlap of locality of query keywords. We use the overlap of locality of query keywords because we mainly
focus on and queries, where keywords should be related to each other in correct answers. If we focus on
also queries, the overlap of locality of query keywords
are not necessarily important, and the size of subgraphs
should be the only important factor for ranking. If we

The class of also queries is the most general class including all conjunctive queries. A typical example ofalso query is a query with keywords “Aug. 1999” and“ACM”, whose intention is to retrieve homepages forany events in July 1999 sponsored by ACM. In thisquery, July 1999 and ACM are not directly related to
one another. They are independently narrowing down
the topic from different aspects.
and queries are the special case of also queries, where21focus on of queries, the shape of graphs and how query
keywords appear in the subgraph (e.g. the order) may
be additional meaningful information for better ranking. The verification of these idea, the support of morethan one kind of conjunctive queries and providing different ranking functions for them, with experiments is a
future issue.

Identifying hierarchies and useful metrics. ACM
TOIS, 10(2):142–180, Apr. 1992.
2. Rodrigo A. Botafogo and Ben Shneiderman. Identifying aggregates in hypertext structures. In Proc.
of ACM Hypertext, pages 63–74, Dec. 1991.
3. Sergey Brin and Lawrence Page. The anatomy ofa large-scale hypertextual web search engine. In
Proc. of 7th Intl. WWW Conf., Apr. 1998.

As discussed above, when we focus on and queries, relation between the occurrences of query keywords isvery important. When we use subgraphs as the logical information unit for retrieval, relation between keywords and anchors pointing to other pages where otherkeywords occur is also very important. For example, if
a keyword occurs in the anchor string of some link, andanother keyword occurs in the page pointed by that link,then those two keywords must be strongly related in that
document. There are a couple of researches that proposed to include words in anchor strings into indexesof pointed pages [20, 3, 17, 21]. When we introduce
the minimal subgraph approach, we also need to examine the relation between the pointed page and all theoccurrences of query keywords in the source page ofthe anchor. The method explained in the subsection 3.4
must easily be extended to include the relation between
keywords and anchors. This is another future issue.

4. Jeromy Carrière and Rick Kazman. WebQuery:
Searching and visualizing the web through connectivity. In Proc. of 6th Intl. WWW Conference,
Apr. 1997.
5. W. Bruce Croft and Howard R. Turtle. A retrieval
model for incorporating hypertext links. In Proc.
of ACM Hypertext, pages 213–224, Nov. 1989.
6. David Gibson, Jon Kleinberg, and Prabhakar
Raghavan. Inferring web communities from link
topology. In Proc. of ACM Hypertext, pages 225–
234, Jun. 1998.
7. http://www.goo.ne.jp.
8. Masanori Harada, Shin-ya Sato, and Kazuhiro
Kazama. Estimation of hierarchical structure of
Web for search engine. IPSJ SIG Notes 99-DBS118/98-FI-54, pages 105–112, May 1999. In
Japanese.

5 CONCLUSION

In this paper, we developed a couple of new techniques
for the retrieval of logical information unit in Web data
based on the minimal subgraph approach. First, we proposed the concept of route links, which are links thatare meant to be the standard browsing routes within asingle information unit, and developed a method to distinguish them from other kinds of links. Second, we
designed a new formula for the ranking of minimal subgraphs including all the given query keywords. It ranks
subgraphs based on the distribution of query keywords
within subgraphs. Third, we proposed a extension tothat formula which takes into consideration not only
distribution of keywords within a subgraph but also distribution of keywords within a page. For the first andthe second one, we showed simple experiments. For thethird one, the verification of the idea with experiments
is a future issue.

9. Kenji Hatano, Ryouichi Sano, Yiewi Duan, andKatsumi Tanaka. An interactive classificationof Web documents by self-organizing maps andsearch engine.
In Proc. of 6th Intl. Conf.
on Database Systems for Advanced Applications(DASFAA’99), pages 35–42. IEEE Computer Society Press, Apr. 1999.
10. Marti A. Hearst and Christian Plaunt. Subtopic
structuring for full-length document access. In
Proc. of ACM SIGIR, pages 59–68, Jun. 1993.
11. Masatsugu Kitagawa, Yoshiaki Mizuuchi, Keishi
Tajima, and Katsumi Tanaka. Clustering and cut
detection for information organization of mailing list. In Proc. of Data Engineering Workshop(DEWS’97), pages 221–226. IEICE, Mar. 1997. In
Japanese.

REFERENCES

1. Rodrigo A. Botafogo, Ehud Rivlin, and Ben
Shneiderman. Structural analysis of hypertexts:
2212. Jon Kleinberg. Authoritative sources in a hyperlinked environment. In Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA), pages
668–677, Jan. 1998.

23. Takuhiro Nagafuji and Motomichi Toyama. A
WWW search engine based on disjoint pagegroups in dividing WWW hyper-text space. In
Proc. of Data Engineering Workshop (DEWS’98).
IEICE, Mar. 1998. In Japanese.

13. Nobuyuki Kobayashi and Fumio Kitagawa. Finding a page-set in the WWW document and its application to search engines. In Proc. of Data Engineering Workshop (DEWS’99). IEICE, Mar. 1999.
In Japanese.

24. Peter Pirolli, James Pitkow, and Ramana Rao. Silk
from a Sow’s ear: Extracting usable structuresfrom the web. In Proc. of ACM SIGCHI Conf.,
pages 118–125, Apr. 1996.
25. Ellen Spertus. ParaSite: Mining structural information on the web. In Proc. of 6th Intl. WWW
Conference, Apr. 1997.

14. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. Trawling the
web for emerging cyber-communities. In Proc. of
7th Intl. WWW Conf., Apr. 1998.

26. Keishi Tajima, Yoshiaki Mizuuchi, Masatsugu
Kitagawa, and Katsumi Tanaka. Cut as a querying
unit for WWW, Netnews, and E-mail. In Proc. of
ACM Hypertext, pages 235–244, Jun. 1998.

15. Sadao Kurohashi, Nobuyuki Shiraki, and Makoto
Nagao. A method for detecting important descriptions of a word based on its density distribution
in text. Transactions of Information Processing
Society of Japan, 38(4):845–854, Apr. 1997. In
Japanese.

27. Ron Weiss, Bienvenido Vélez, Mark A. Sheldon, Chanatip Namprempre, Peter Szilagyi, Andrezej Duda, and David K. Gifford. HyPursuit:
A hierarchical network search engine that exploits
content-link hypertext clustering. In Proc. of ACM
Hypertext, pages 180–193, 1996.

16. Wen-Syan Li and Yi-Leh Wu. Query relaxation
by structure for Web document retrieval with progressive processing (extended abstract). In Proc.
of Advanced Database Symposium, pages 19–25.
IPSJ, Dec. 1998.
17. Yanhong Li. Toward a qualitative search engine. IEEE Internet Computing, 2(4):24–29,
July/August 1998.
18. http://www.linpro.no/lwp/.
19. Massimo Marchiori. The quest for correct information on the web: Hyper search engines. In
Proc. of 6th Intl. WWW Conference, Apr. 1997.
20. Oliver A. McBryan. GENVL and WWWW: Tools
for taming the web. In Proc. of 1st Intl. WWW
Conf., may 1994.
21. Yoshiaki Mizuuchi and Keishi Tajima. Finding
context paths for Web pages. In Proc. of ACM
Hypertext, pages 13–22, Feb. 1999.
22. Yoshiaki Mizuuchi, Keishi Tajima, and Katsumi
Tanaka. Retrieval of graph structured data basedon cut partitioning. IPSJ SIG Notes 97-DBS-113,
pages 281–286, Jul. 1997. In Japanese.
23