Information Technology Reference
In-Depth Information
Given a prefix < P
0
, P
1
, P
2
,....,P
i
>, of a session < P
0
, P
1
, P
2
,….,P
n
>, a shortcut to P
n
, i.e. , P
i+1
-> P
n
, can
be added to page P
i+1
. In MINPATH, the expected saving of the shortcut is calculated as the product of the
number of links saved by following that particular shortcut and the probability that P
n
is the destination
page. Instead, we compute the expected saving as a cost function of page size and page probability.
The cost of browsing a page P
k
, cost(P
k
), is composed of the times to download the page, to view the
page, and to click the link for next page. In other words, if a page is skipped by following a shortcut,
the times to download, view, and click the page, are saved. The time to view and click is constant, but
the time to download depends on page size. A parameter, ∆, is introduced to represent the download
cost, which can be thought as time for transmission a unit of data. By introducing ∆, download time is
separated from view and click time. The value of ∆ is determined by network bandwidth and congestion.
Since the cost function is relative, i.e., only the ratio of download time to view and click time matters,
the view and click time is normalized to 1 in the cost function and ∆ is adjusted accordingly.
Cost(P
k
) = download time + view and click time = Size(P
k
)*∆+1
(1)
where Size(P
k
) is the size of page P
k
in kilobytes.
The saving of a shortcut is the sum of the costs of pages skipped.
Expected savings (P
i+1
-> P
n
) =
N
−
1
P
s
*{
∑
Cost(P
k
)} =
k i
= +
2
N
−
1
P
s
*{
∑
[Size(Pk)*∆+1 ]}
(2)
k i
= +
2
where P
s
is the probability that page P
n
is the destination page.
In our experiments, we found ∆ has little effect on results, because pages have similar sizes. Its value
is fixed at 0.5 assuming an effective bandwidth of 1 kbps and view and click time of 2 seconds. When
pages have quite different sizes, ∆ may have an impact on results.
To differentiate, we call the modified algorithm MINCOST since it takes into consideration cost for
downloading. MINPATH considers only savings in view and click time, while MINCOST considers
both view and click time and download time. It is easy to see that MINCOST is a generalization of
MINPATH. When ∆ is set to 0, the cost function in (2) degrades into the number of links saved which
is used in MINPATH.
Perfor MAnCe eVALuATIon
The MINCOST algorithm is implemented in the C programming language and experiments are per-
formed to evaluate the efficiency of our approach to improve mobile Web navigation with real datasets.
The experiments are run on a PC with a 2.66 GHz Intel Pentium 4 processor, a memory of 512 MB,
and running Windows XP professional.
Search WWH ::
Custom Search