Improving Mobile Web Navigation Using N-Grams Prediction Models - Distributed Artificial Intelligence, Agent Technology, and Collaborative Applications - page 319

Table 1. A 3-gram prediction table

Predicted
next page

Probability of
next page

3-gram

A, B, C D 1.0000

B, C, D G 0.5000

B, C, D H 0.5000

Figure 1. Algorithm for constructing N-gram models

Input:
L: sessions from Web server logs.
N: order of N-gram
Output:
T: N-gram prediction table
// for an N-gram P and a predicted next page C, cell T[P, C] stores the probability.

Procedure:
Begin
For i = 1 to |L| do // for every session
S = L[i]; // the i-th session
For j =1 to |S| do // |S| represents the number of pages in session S
If (|S| - j)> N // Find a sub-string of length N starting at j
P = sub-string (S, j, N); // the j-th N-gram
//sub-string returns N consecutive pages in S,
// starting from j-th page,
C = sub-string(S, j+N, 1); // Find the next page
T [P, C] = T [P, C] + 1; // increment count of (N-gram, next page) pair
End If
End For
End For
For each [P, C] in T

T [P, C] = T [P, C] / Σ C (T[P, C]); // convert count into probability

End For
Return T;
End

Shortcut r ecommendation

The MINPATH algorithm ranks shortcuts based on their expected savings. In computing expected sav-
ings, MINPATH considers only the number of links saved. We modified MINPATH to reflect expected
saving in total cost.