'$

Discovery and Retrieval of Logical Information Units in Web
Keishi Tajima Kenji Hatano Takeshi Matsukura
Ryouichi Sano Katsumi Tanaka
Department of Computer and Systems Engineering
Kobe University&%

'$Background (1/3)
Access to Web Pages
There are three ways to access Web pages:
1. direct access by known URLs,
2. navigation from other pages, and
3. content-based access via search engines.
Each page is indexed based on the words appearing in it.

&1%

'$Background (2/3)
Two Types of Queries
1. retrieving an already-known page out of huge Web data.
• We use keywords that we saw in that page.
• The querying unit may be a page.
2. looking for unknown documents concerned with a topic of one’s
current interest.
• We use keywords that are likely to appear in documents
concerned with that topic.
• The querying unit is a document

&2%

'$

Background (3/3)
Pages v.s. Documents• Pages — physical data units designed for presentation.
• Documents — logical data units consisting of independent
self-contained set of information.
One complete document in Web isoften composed of multiple pages.

&3%

'$Problem
Data Unit in Web Query
A Data unit in ordinary search engines is not a documents but apage. For this discrepancy,
conjunctive queries
with multiple keywords
may fail to retrieve anappropriate document.

Web

retrieval
document 1
document 2

query = {Web, retrieval}
&4%

'$

Goal of This Research

The main goal of this research is:
to develop a framework for querying
logical documents in Web data.

&5%

'$Related Work (1/4)
Classification (1): Static v.s. Dynamic
Static Approach:statically divides the Web graph into subgraphs
corresponding to logical data units in advance.
• the most straightforward consequence of our observation of theproblem.
• we can employ complex computation for data unit discovery
without the response latency at query execution.

&6%

'$Related Work (2/4)
Classification (1): Static v.s. Dynamic
Dynamic Approach:dynamically determines the data units
when a query is given• The units may vary depending on the given query.
• By combining with some ranking method, it can always return “thebest n” candidates [Li98].

&

7%

'$Related Work (3/4)
Classification (2): Information Used for Data Unit Detection• page contents– text– tagging pattern• graph structure• directory structure in URL&8%

'$Related Work (4/4)• Static / Term Frequency [Mizuuchi97,Tajima98]
repeatedly merging neighboring nodes based on the term
frequency similarity• Static / Link and Directory Structure [Nagafuji98]
repeatedly merging and splitting directories based on the structuresof links between directories.
• Dynamic / Graph Structure“minimal subgraph approach” [Li98,Hatano99](the only dynamic approach published so far)find minimal subgraphs including all the keywords
&9%

'$

Our Approach (1/3)
We take minimal subgraph approach
Though the static approach is a straightforward solution,• it is difficult to perfectly detect logical data units, and• always returning “best n candidates” is very useful.

&10%

'$

Our Approach (2/3)
Issues in the Minimal Subgraph Approach
1. The cost to dynamically compute minimal subgraphs is high.
We detect links that are clearly not parts of a logical
data unit, and does not traverse them.
2. Not all subgraphs are part of one logical document. Someranking method is essential to give priority to likely ones.
We designed a ranking methods based on how strongly
the keywords appearing in a subgraph seem related toeach other.

&11%

'$

Our Approach (3/3)
Summary of Our Approach
Given query keywords, we approximate logical data units including
all the given keywords by the following steps:
1. we determine links that may be parts of a logical document,
2. we find minimal subgraphs connected only by those links andincluding all the given keywords, and3. we rank them by our formula.

&12%

'$

Step 1: Determining Links to Traverse (1/3)
Typical Structure of Documents in Web• sequence — pages corresponding to sections of a document linked
via “next” and “previous” links, e.g.:– html versions of papers or slides.
• hierarchy — pages with hierarchical indexing structure, e.g.:– many homepages of people or organizations, or– database pages, such as product catalog pages.

&13%

'$Step 1: Determining Links to Traverse (2/3)
Three Kinds of Links
1. jump links — to pages in other documents by other authors,
2. route links — intended by page authors to be “standard routes”
through which the readers go through the document, and3. back links — going back to some prior pages along the routes.
a document ≡ a subgraph connected by “route links”

&14%

'$

Step 1: Determining Links to Traverse (3/3)
Excluding Non-Route Links
We exclude links that point to:
1. pages in ancestor directories,
2. “index.*” or the directory name of the same directory
3. pages in an incomparable, not sibling directory, or
4. pages on a different Web site
We use very simple analysis because:• we only want to exclude clearly wrong ones, and• our purpose is to reduce the cost&15%

'$

Step 2: Finding Minimal Subgraphs
Our current implementation uses the result of an existing searchengine.
1. first we fetch pages including at least one keyword by submitting
a disjunctive query to the search engine,
2. we fetch the pages in a distance 1 via “route links” from retrieved
pages
3. repeat the step 2 until enough number of answers are found.
For a real system with its own database, we need to elaborate somealgorithm to traverse a graph. See [Li98].

&16%

'$

Step 3: Ranking Method
Cost Function F (G)F (G) calculates the “cost” of a subgraph G:
F (G) =∑

−1(K(v)+C)
v∈V

where V :a set of pages in GK(v): the number of keywords in the page v
C:a constant parameter to adjust FA “cost” of a page v is smaller when K(v) is larger.
We rank G with smaller F (G) higher.
&17%

'$

Step 3: Ranking Method
Properties of F (G)F (G) = n ·1∑−1(K(v)+C)v∈Vn
where n is the number of pages in V .

1. F (G) is proportional to n, i.e. the size of the subgraph.
2. roughly, F (G) is inversely proportional to the average of K(v)

&18%

'$

Step 3: Ranking Method
Properties of F (G) (cont’d)
3. the larger the variation of K(v) is, the larger F (G) is.
1 ∑1 ∑−1(K(v) + C)≥{(K(v) + C)}−1nnv∈Vv∈V“=” holds only when ∀vi, vj .K(vi) = K(vj ).
4. The smaller C is, the more significant the effect of K(v) is.
When C = 0, the cost of a page with no keyword is infinite.
5. F (G) does not reflect the shapes of G, which heavily depends
on the authoring style of authors.
&19%

'$

Step 3: Ranking Method
Gn avg(K(v)) C = 3 C = 1 C = 0

1a,bb,c2a,bc2a,bbb,c 3a,bbc3a,bb,c 3
ab
c
3
a,bc
3
a,b,c&

3
2
1.5
1.67
1.33
1.33
11

0.167
0.400
0.450
0.650
0.700
0.733
0.750
0.783

0.250
0.677
0.833
1.167
1.333
1.677
1.500
1.833

0.333
1.000
1.500
2.000
2.500
∞
3.000
∞
20%

'$

Step 3: Ranking Method
Summary of Properties of F (G)F (G) reflects the distribution of locality of keywords.
• When keywords are distributed to many pages, n becomes large.
• The more the localities of keywords overlap, the larger the average
number of K(v) is.
• When keywords are continuously overlapping in every page, they
are more likely to be one document related to those keywords.

&21%

'$

Step 3: Ranking Method
Distribution within Pages• F (G) reflects the distribution of keywords across pages.
• We should also examine the distribution within each page.
e.g.

Links to My Favorite Pages• ’xxx’ Home Page — . . . k1 . . .
• Pages on ’yyy’ — . . .
..
• Pages by ’yyy’ — . . . k2 . . .

&22%

'$

Step 3: Ranking Method
Appearance Density of Words• Each word occurrence has its influence around it.
• dt(i): appearance density of a word t at a position i is the sum of
the influences of the occurrence of t around i.
• We normalize dt(i) so that max(dt(i)) = 1
id(i)

d(i)

t1

t1
t1
t1
i&i
23%

'$

Step 3: Ranking Method
Appearance Density of Wordsr(t1, t2), the degree of the interrelation of t1 and t2:
r(t1, t2) = max min(dt1 (i), dt2 (i))
1≤i≤L

d(i)

t1

t2

r(t1, t2)iFor word t in the <title> tag or the main heading:r(t, t0) = 1 for all t0&24%

'$

Step 3: Ranking Method
Appearance Density of Words
We redefine F (G) so that it reflects the interrelation of keywords
within pages:
F (G) =∑v∈V{A · K(v) + B ·∑r(ti, tj ) + C}−1ti,tj ∈T (v)• We will find appropriate values for A, B, C by experiments.

&25%

'$

Preliminary Experiments (1/2)
Query 1: {notebook, card, catalog}“collect all the catalog pages of PC cards for laptop computers”
n12345# of ans.
980
272100# of correct ans. 682
171200precision ratio 0.696 0.629 0.571––(accumulative) 0.696 0.694 0.691 0.691 0.691
recall ratio†
0.959 0.983 1.000 1.000 1.000† We assume there is no answer with n > 5&26%

'$Preliminary Experiments (2/2)
Query 2: {“Ryouichi Sano,” “Kobe University”}“find the homepage of Ryouichi Sano, who is a student of KobeUniversity”
n1 2 3 4 5# of ans.
0 0 1 1 0
# of correct ans. 0 0 0 1 0&27%

'$Discussion (1/3)
When is the minimal subgraph approach useful?
• recall-oriented queries, e.g. “collect all pages that . . . ”• to find some specific page. Some keywords that is expected to beappropriate for the query may happen to appear only inneighboring pages.

&28%

'$Discussion (2/3)
Semantics of Conjunctive Web Queries
Conjunctions are used with various intentions:also query — a page discussing t1, and also t2.
t1 and t2 may not be related to each other.
and query — a page discussing a topic related to t1 and t2.
t1 and t2 are cooperatively describing the topic.
of query — a page discussing t1 of t2.
General word t2 andspecialized word t1
narrow down the topic
stepwise.
&also
andof

29%

'$Discussion (3/3)
Ranking Method for Each Semantics• also query
The interrelation between keywords may not be important, andtherefore, K(v) and r(t1, t2) are not appropriate.
• and query
We mainly focus on this. K(v) and r(t1, t2) must be important.
• of query
The shape of the graphs and the order of the appearance of thewords may also be useful.

&30%

'$Conclusion• logical data unit in Web 6= page
• minimal subgraph based retrieval for conjunctive queries• distinction of “route links” and other links• ranking subgraphs based on the overlap/distribution of query
keywords&31%