Efficient Data Mining for Path Traversal Patterns.
AbstractIn this paper, we explore a new data mining capability that involves mining path traversal patterns in a distributed information-providing environment where documents or objects are linked together to facilitate interactive access. Our solution procedure consists of two steps. First, we derive an algorithm to convert the original sequence of log data into a set of maximal forward references. By doing so, we can filter out the effect of some backward references, which are mainly made for ease of traveling and concentrate on mining meaningful user access sequences. Second, we derive algorithms to determine the frequent traversal patternsi.e., large reference sequencesfrom the maximal forward references obtained. Two algorithms are devised for determining large reference sequences; one is based on some hashing and pruning techniques, and the other is further improved with the option of determining large reference sequences in batch so as to reduce the number of database scans required. Performance of these two methods is comparatively analyzed. It is shown that the option of selective scan is very advantageous and can lead to prominent performance improvement. Sensitivity analysis on various parameters is conducted.
Introduction
Due to the increasing use of computing for various applications, the importance of database mining
is growing at a rapid pace recently. Progress in bar-code technology has made it possible for
retail organizations to collect and store massive amounts of sales data. Catalog companies can also
collect sales data from the orders they received. It is noted that analysis of past transaction data
can provide very valuable information on customer buying behavior, and thus improve the quality
of business decisions (such as what to put on sale, which merchandises to be placed together on
shelves, how to customize marketing programs, to name a few). It is essential to collect a sufficient
amount of sales data before any meaningful conclusion can be drawn therefrom. As a result, the
amount of these processed data tends to be huge. It is hence important to devise efficient algorithms
to conduct mining on these data.
Note that various data mining capabilities have been explored in the literature. One of the
most important data mining problems is mining association rules [3, 4, 13, 15]. For example, given
a database of sales transactions, it is desirable to discover all associations among items such that
the presence of some items in a transaction will imply the presence of other items in the same
transaction. Also, mining classification is an approach of trying to develop rules to group data
tuples together based on certain common features. This has been explored both in the AI domain
[16, 17] and in the context of databases [2, 6, 12]. Mining in spatial databases was conducted in
[14]. Another source of data mining is on ordered data, such as stock market and point of sales
data. Interesting aspects to explore from these ordered data include searching for similar sequences
[1, 19], e.g., stocks with similar movement in stock prices, and sequential patterns [5], e.g., grocery
items bought over a set of visits in sequence. It is noted that data mining is a very application-dependent
issue and different applications explored will require different mining techniques to cope
with. Proper problem identification and formulation is therefore a very important part of the whole
knowledge discovery process.
In this paper, we shall explore a new data mining capability which involves mining access patterns
in a distributed information providing environment where documents or objects are linked
together to facilitate interactive access. Examples for such information providing environments
include World Wide Web (WWW) [11] and on-line services, such as Prodigy, CompuServe and
America Online, where users, when seeking for information of interest, travel from one object to
another via the corresponding facilities (i.e., hyperlinks) provided. Clearly, understanding user
access patterns in such environments will not only help improve the system design (e.g., provide
efficient access between highly correlated objects, better authoring design for pages, etc.) but also
be able to lead to better marketing decisions (e.g., putting advertisements in proper places, better
customer/user classification and behavior analysis, etc. Capturing user access patterns in such
environments is referred to as mining traversal patterns in this paper. Note that although some
efforts have elaborated upon analyzing the user behavior [8, 9, 10], there is little result reported
on dealing with the algorithmic aspects to improve the execution of traversal pattern mining. This
can be in part explained by the reason that these information providing services, though with great
potential, are mostly in their infancy and their customer analysis may still remain in a coarser
level such as user occupation/age study. In addition, it is important to note that, as pointed out
in [8], since users are traveling along the information providing services to search for the desired
information, some objects are visited because of their locations rather than their content, showing
the very difference between the traversal pattern problem and others which are mainly based on
customer transactions. This unique feature of the traversal pattern problem unavoidably increases
the difficulty of extracting meaningful information from a sequence of traversal data. However, as
these information providing services are becoming increasingly popular nowadays, there is a growing
demand for capturing user behavior and improving the quality of such services. As a result,
the problem of mining traversal patterns has become too important not to address immediately.
Consequently, we shall explore in this paper the problem of mining traversal patterns. Our solution
procedure consists of two steps. First, we derive an algorithm, called algorithm MF (standing
for maximal forward references), to convert the original sequence of log data into a set of traversal
subsequences. As defined in Section 2, each traversal subsequence represents a maximal forward
reference from the starting point of a user access. As will be explained later, this step of converting
the original log sequence into a set of maximal forward references will filter out the effect of
backward references which are mainly made for ease of traveling, and enable us to concentrate on
mining meaningful user access sequences. Second, we derive algorithms to determine the frequent
traversal patterns, termed large reference sequences, from the maximal forward references obtained
above, where a large reference sequence is a reference sequence that appeared in a sufficient number
of times in the database. Note that the problem of finding large reference sequences is similar to
that of finding large itemsets for association rules [3] where a large itemset is a set of items appearing
in a sufficient number of transactions. However, they are different from each other in that
a reference sequence in mining traversal patterns has to be consecutive references in a maximal
forward reference whereas a large itemset in mining association rules is just a combination of items
in a transaction. As a consequence, although several schemes for mining association rules have
been reported in the literature [3, 4, 15], the very difference between these two problems calls for
the design of new algorithms for determining large reference sequences.
Explicitly, we devise two algorithms for determining large reference sequences. The first one,
referred to as full-scan (FS) algorithm, essentially utilizes some techniques on hashing and pruning
while solving the discrepancy between traversal patterns and association rules mentioned above.
Although trimming the transaction database as it proceeds to later passes, algorithm FS is required
to scan the transaction database in each pass. In contrast, by properly utilizing the candidate reference
sequences, the second algorithm devised, referred to as selective-scan (SS) algorithm, is able
to avoid database scans in some passes so as to reduce the disk I/O cost involved. Specifically,
algorithm SS has the option of using a candidate reference set to generate subsequent candidate reference
sets, and delaying the determination of large reference sets to a later pass when the database
is scanned. Since SS does not scan the database to obtain a large reference set in each pass, some
database scans are saved. Experimental studies are conducted by using a synthetic workload that is
generated based on referencing some logged traces, and performance of these two methods, FS and
SS, is comparatively analyzed. It is shown that the option of selective scan is very advantageous
and algorithm SS thereby outperforms algorithm FS in general. Sensitivity analysis on various
parameters is also conducted.
This paper is organized as follows. Problem formulation is given in Section 2. Algorithm MF to
identify maximal forward references is described in Section 3.1, and two algorithms, FS and SS, for
determining large reference sequences are given in Section 3.2. Performance results are presented
in Section 4. Section 5 contains the summary.
Problem Formulation
As pointed out earlier, in an information providing environment where objects are linked together,
users are apt to traverse objects back and forth in accordance with the links and icons provided. As
a result, some node might be revisited because of its location, rather than its content. For example,
in a WWW environment, to reach a sibling node a user is usually inclined to use "backward" icon
and then a forward selection, instead of opening a new URL. Consequently, to extract meaningful
user access patterns from the original log database, we naturally want to take into consideration
the effect of such backward traversals and discover the real access patterns of interest. In view of
this, we assume in this paper that a backward reference is mainly made for ease of traveling but
not for browsing, and concentrate on the discovery of forward reference patterns. Specifically, a
backward reference means revisiting a previously visited object by the same user access. When
backward references occur, a forward reference path terminates. This resulting forward reference
path is termed a maximal forward reference. After a maximal forward reference is obtained, we
back track to the starting point of the forward referencing and resume another forward reference
path. In addition, the occurrence of a null source node also indicates the termination of an ongoing
forward reference path and the beginning of a new one.
While deferring the formal description of the algorithm to determine maximal forward references
(i.e., algorithm MF) to Section 3.1, we give an illustrative example for maximal forward
references below. Suppose the traversal log contains the following traversal path for a user:
G; H; G; W; A; O; U; O; V g, as shown in Figure 1. Then, it can be verified
by algorithm MF that the set of maximal forward references for this user is fABCD;ABEGH;
g. After maximal forward references for all users are obtained, we then map
the problem of finding frequent traversal patterns into the one of finding frequent occurring consecutive
subsequences among all maximal forward references. A large reference sequence is a reference
sequence that appeared in a sufficient number of times. In a set of maximal forward references,
the number of times a reference sequence has to appear in order to be qualified as a large reference
sequence is called the minimal support. A large k-reference is a large reference sequence with k
elements. We denote the set of large k-references as L k and its candidate set as C k , where C k ,
as obtained from L k\Gamma1 [4], contains those k-references that may appear in L k . Explicitly, C k is a
superset of L k .
It is worth mentioning that after large reference sequences are determined, maximal reference
sequences can then be obtained in a straightforward manner. A maximal reference sequence is
a large reference sequence that is not contained in any other maximal reference sequence. For
example, suppose that fAB; BE;AD;CG;GH;BGg is the set of large 2-references (i.e., L 2 ) and
fABE;CGHg is the set of large 3-references (i.e., L 3 ). Then, the resulting maximal reference
sequences are AD;BG;ABE; and CGH . A maximal reference sequence corresponds to a "hot"
access pattern in an information providing service. In all, the entire procedure for mining traversal
patterns can be summarized as follows.
Procedure for mining traversal patterns:
Step 1: Determine maximal forward references from the original log data.
G
A
O

Figure

1: An illustrative example for traversal patterns.
Step 2: Determine large reference sequences (i.e., L k , k - 1) from the set of maximal forward
references.
Step 3: Determine maximal reference sequences from large reference sequences.
Since the extraction of maximal reference sequences from large reference sequences (i.e., Step
is straightforward, we shall henceforth focus on Steps 1 and 2, and devise algorithms for the
efficient determination of large reference sequences.
3 Algorithm for Traversal Pattern
We shall describe in Section 3.1 algorithm MF which converts the original traversal sequence into
a set of maximal forward references. Then, by mapping the problem of finding frequent traversal
patterns into the one of finding frequent consecutive subsequences, we develop two algorithms,
called full-scan (FS) and selective-scan (SS), for mining traversal patterns.
3.1 Maximal Forward References
In general, a traversal log database contains, for each link traversed, a pair of (source, desti-
nation). This part of log database is called referer log [7]. For the beginning of a new path,
which is not linked to the previous traversal, the source node is null. Given a traversal sequence
of a user, we shall map it into multiple subsequences, each of which
represents a maximal forward reference. The algorithm for finding all maximal forward references is
given as follows. First, the traversal log database is sorted by user id's, resulting in a traversal path,
for each user, where pairs of (s are ordered by time. Algorithm
MF is then applied to each user path to determine all of its maximal forward references. Let D F
denote the database to store all the resulting maximal forward references obtained.
Algorithm An algorithm to find maximal forward references.
string Y to null for initialization, where string Y is used to store the current
forward reference path. Also, set the flag to indicate a forward traversal.
Step 2: Let
If A is equal to null then
/* this is the beginning of a new traversal */
begin
Write out the current string Y (if not null) to the database D F ;
string
Go to Step 5.
Step 3: If B is equal to some reference (say the j-th reference) in string Y then
/* this is a cross-referencing back to a previous reference */
begin
If F is equal to 1 then write out string Y to database D F ;
Discard all the references after the j-th one in string Y ;
Go to Step 5.
Step 4: Otherwise, append B to the end of string Y .
/* we are continuing a forward traversal */
If F is equal to 0, set
Step 5: Set 1. If the sequence is not completed scanned then go to Step 2.
Consider the traversal scenario in Figure 1 for example. It can be verified that the first backward
reference is encountered in the 4-th move (i.e., from D to C). At that point, the maximal
forward reference ABCD is written to D F (by Step 3). In the next move (i.e., from C to B),
although the first conditional statement in Step 3 is again true, nothing is written to D F since the
flag meaning that it is in a reverse traversal. The subsequent forward references will put
ABEGH into the string Y , which is then written to D F when a reverse reference (from H to G)

Table

1: An example execution by algorithm MF.
move string Y output to D F
9 ABEG ABEGH
14 AO AOU
is encountered. The execution scenario by algorithm MF for the input in Figure 1 is given in Table 1.
It is noted that in some cases, the traversal log record obtained only contains the destination references
instead of a pair of references. For example, for WWW browsing, the request message may
only contain the destination URL. The traversal sequence will then have the form fd
for each user. Even with such an input, we can still convert it into a set of maximal forward
references. The only difference is that in this case we cannot identify the breakpoint where the user
picks a new URL to begin a new traversal path, meaning that two consecutive maximal forward
references. For example, ABEH and WXY Z, may be treated as one path, i.e., ABEHWXYZ.
Certainly, this constraint, i.e., without the id's of source nodes, could increase the computational
complexity because the paths considered become longer. However, this constraint should have little
effect on identifying frequent reference subsequences. Since there is no logical link between H and
W , a subsequence containing HW is unlikely to occur frequently. Hence, a reference containing
the pattern HW will unlikely emerge as a large reference later. Therefore, algorithm MF can in
fact be employed for the cases when the id's of source nodes are not available.
3.2 Determining Large Reference Sequences
Once the database containing all maximal forward references for all users, D F , is constructed, we
can derive the frequent traversal patterns by identifying the frequent occurring reference sequences
in D F . A sequence s 1 ; ::::; s n is said to contain r 1 ; ::::; r k as a consecutive subsequence if there exists
an i such that s k. For example, BAHPM is said to contain AHP . A sequence
of k references, r 1 ; ::::; r k , is called a large k-reference sequence, if there are a sufficient number of
users with maximal forward references in D F containing r 1 ; ::::; r k as a consecutive subsequence.
As pointed out before, the problem of finding large reference sequences is different from that
of finding large itemsets for association rules and thus calls for the design of new algorithms.
Consequently, we shall derive in this paper two algorithms for mining traversal patterns. The first
one, called full-scan (FS) algorithm, essentially utilizes the concept of DHP [15] (i.e., hashing and
pruning) while solving the discrepancy between traversal patterns and association rules. DHP has
two major features in determining association rules: one is efficient generation for large itemsets and
the other is effective reduction on transaction database size after each scan. Although trimming the
transaction database as it proceeds to later passes, FS is required to scan the transaction database
in each pass. In contrast, by properly utilizing the candidate reference sequences, the second
algorithm, referred to as selective-scan (SS) algorithm, is improved with the option of determining
large reference sequences in batch so as to reduce the number of database scans required.
3.2.1 Algorithm on Full Scan
Algorithm FS utilizes key ideas of the DHP algorithm. The details of DHP can be found in [15]. An
example scenario for determining large itemsets and candidate itemsets is given in the Appendix 1 .
As shown in [15], by utilizing a hash technique, DHP is very efficient for the generation of candidate
itemsets, in particular for the large 2-itemsets, thus greatly improving the performance bottleneck
of the whole process. In addition, DHP employs effective pruning techniques to progressively reduce
the transaction database size.
Recall that L k represents the set of all large k-references and C k is a set of candidate k-references.
C k is in general a superset of L k . By scanning through D F , FS gets L 1 and makes a hash table (i.e.,
to count the number of occurrences of each 2-reference. Similarly to DHP, starting with
FS generates C k based on the hash table count obtained in the previous pass, determines the set of
1 In this example, the technique of hashing, which is employed by DHP to reduce the number of candidate itemsets,
is not shown.
large k-references, reduces the size of database for the next pass, and makes a hash table to determine
the candidate 1)-references. Note that as in mining association rules, a set of candidate
references, C k , can be generated from joining L k\Gamma1 with itself, denoted by L
due to the difference between traversal patterns and association rules, we modify this approach
as follows. For any two distinct reference sequences in L
join them together to form a k-reference sequence only if either r contains s
after dropping the first element in one sequence and the last
element in the other sequence, the remaining two are identical). We note that
when k is small (especially for the case of deriving C k by joining L k\Gamma1 with itself will result
in a very large number of candidate references and the hashing technique is thus very helpful for
such a case. As k increases, the size of L decrease significantly. Same as in [15], we
found that it is generally beneficial for FS to generate C k directly from L
using hashing) once k - 3.
To count the occurrences of each k-reference in C k to determine L k , we need to scan through a
trimmed version of database D F . From the set of maximal forward references, we determine, among
k-references in C k , large k-references. After the scan of the entire database, those k-references in
C k with count exceeding the threshold become L k . If L k is non-empty, the iteration continues for
the next pass, i.e., pass k + 1. Same as in DHP, every time when the database is scanned, the
database is trimmed by FS to improve the efficiency of future scans.
3.2.2 Algorithm on Selective Scan (SS)
Algorithm SS is similar to algorithm FS in that it also employs hashing and pruning techniques to
reduce both CPU and I/O costs, but is different from the latter in that algorithm SS, by properly
utilizing the information in candidate references in prior passes, is able to avoid database scans in
some passes, thus further reducing the disk I/O cost. The method for SS to avoid some database
scans and reduce disk I/O cost is described below. Recall that algorithm FS generates a small
number of candidate 2-references by using a hashing technique. In fact, this small C 2 can be used
to generate the candidate 3-references. Clearly, a C 0
3 generated from C 2   C 2 , instead of from L 2   L 2 ,
will have a size greater than jC 3 j where C 3 is generated from L 2   L 2 . However, if jC 0
3 j is not much
larger than jC 3 j, and both C 2 and C 0
3 can be stored in the main memory, we can find L 2 and L 3
together when the next scan of the database is performed, thereby saving one round of database
This approach of generating Ck directly from Lk\Gamma1 is proposed by algorithm Apriori in [4] in generating candidate
itemsets for association rules.
scan. It can be seen that using this concept, one can determine all L k 's by as few as two scans of
the database (i.e., one initial scan to determine L 1 and a final scan to determine all other large
reference sequences), assuming that C 0
is generated from C 0
be kept in the memory.
Note that when the minimum support is relatively small or potentially large references are
long, C k and L k could become large. With C 0
being generated from C 0
may cost too much CPU time to generate all subsequent C 0
candidate sets of large references since the size of C j may become huge quickly, thus compromising
all the benefit from saving disk I/O cost. For the illustrative example in the Appendix, if C 3 was
determined from C 2   C 2 , instead of from L 2   L 2 , then C 3 would be ffABCg, fABEg, fACEg,
fBCEgg. This fact suggests that a timely database scan to determine large reference sequences
will in fact pay off. After a database scan, one can obtain the large reference sequences which are
not determined thus far (say, up to Lm ) and then construct the set of candidate (m+ 1)-references,
Cm+1 , based on Lm from that point. According to our experiments, we found that if jC 0
for some k - 2, it is usually beneficial to have a database scan to obtain L k+1 before the set of
candidate references becomes too big. (Same as in FS, each time the database is scanned, the
database is trimmed by SS to improve the efficiency of future scans.) We then derive C 0
k+2 from
L k+1 . (We note that C 0
k+2 is in fact equal to C k+2 here.) After that, we again use C 0
j to derive
k+2. The process continues until the set of candidate (j+1)-references becomes empty.
Illustrative examples for FS and SS are given in Table 2 where the number of reference paths
and the minimum support Extensive experiments are conducted in
Section 4. In this example run, FS performs a database scan in each pass to determine the corresponding
large reference sequences, resulting in six database scans. On the other hand, SS scans the
database only three times (skipping database scans in passes 2, 4 and 5), and is able to obtain the
same result. The CPU and disk I/O times for FS are 19.48 seconds and 30.8 seconds, respectively,
whereas those for SS are 18.75 seconds and 17.8 seconds, respectively. Considering both CPU and
I/O times, the execution time ratio for SS to FS is 0.73, showing a prominent advantage of SS.
Performance Results
To assess the performance of FS and SS, we conducted several experiments to determine large
reference sequences by using an RS/6000 workstation with model 560. The methods used to

Table

2: Results from an example run by FS and SS.
Algorithm FS
Algorithm SS
Root
Leaf node
25% go back to parent node
75% jump to only internal node
parent node
jump to internal node
3% of all internal nodes
parent node
children nodes
internal jump
(to any node)
(a) (b)

Figure

2: A traversal tree to simulate WWW.
generate synthetic data are described in Section 4.1. Performance comparison of these two methods
is given in Section 4.2. Sensitivity analysis is conducted in Section 4.3.
4.1 Generation of Synthetic Traversal Paths
In our experiment, the browsing scenario in a World Wide Web (WWW) environment is simulated.
To generate a synthetic workload and determine the values of parameters, we referenced some
logged traces which were collected from a gateway in our working location [18]. First, a traversal
tree is constructed to mimic WWW structure whose starting position is a root node of the tree.
The traversal tree consists of internal nodes and leaf nodes. Figure 2a shows an example of the
traversal tree. The number of child nodes at each internal node, referred to as fanout, is determined
from a uniform distribution within a given range. The height of a subtree whose subroot is a child
node of the root node is determined from a Poisson distribution with mean - h . Then, the height of
a subtree whose subroot is a child of an internal node N i is determined from a Poisson distribution
with mean equal to a fraction of the maximum height of the internal node N i . As such, the height
of a tree is controlled by the value of - h .
A traversal path consists of nodes accessed by a user. The size of each traversal path is picked
from a Poisson distribution with mean equal to jP j. With the first node being the root node, a
traversal path is generated probabilistically within the traversal tree as follows. For each internal
node, we determine which is the next hop according to some predetermined probabilities. Essen-
tially, each edge connecting to an internal node is assigned with a weight. This weight corresponds
to the probability that each edge will be next accessed by the user. As shown in Figure 2b, the
weight to its parent node is assigned with p 0 , which is generally 1
where n is the number of
child nodes. This probability of traveling to each child node, p i , is determined from an exponential
distribution with unit mean, and is so normalized that the sum of the weights for all child nodes is
equal . If this internal node has an internal jump and the weight for this jump is p j , then
is changed to p 0 and the corresponding probability for each child node is changed to
such that the sum of all the probabilities associated with this node remains one. When the
path arrives at a leaf node, the next move would be either to its parent node in backward (with a
probability 0.25) or to any internal node (with an aggregate probability 0.75). Some internal nodes
in the tree have internal jumps which can go to any other nodes. The number of internal nodes
with internal jumps is denoted by N J , which is set to 3% of all the internal nodes in general cases.
The sensitivity of varying N J will also be analyzed. Those nodes with internal jumps are decided
randomly among all the internal nodes. Table 3 summarizes the meaning of various parameters
used in our simulations.
4.2 Performance Comparison between FS and SS

Figure

3 represents execution times of two methods, FS and SS, when
0:1. HxPy means that x is the height of a tree and y is the average size of the reference paths.
D200K means that the number of reference paths is 200,000. A tree for H10 was obtained when
the height of a tree is 10 and the fanout at each internal node is between 4 and 7. The root node
consists of 7 child nodes. The number of internal nodes is 16,200 and the number of leaf nodes is
73,006. The number of internal nodes with internal jumps is thus 16200 \ThetaN J =486. Note that the
CPU
Time
(sec)
Minimum support
c
c
SS \Theta
\Theta \Theta \Theta \Theta \Theta
I/O
Time
(sec)
Minimum support
c c
c
SS \Theta
\Theta \Theta \Theta \Theta \Theta \Theta51525
CPU
Time
(sec)
Minimum support
c c
c
c
c
c
SS \Theta
\Theta \Theta \Theta \Theta
\Theta
I/O
Time
(sec)
Minimum support
c c
c c
c
c
SS \Theta
\Theta \Theta \Theta \Theta \Theta \Theta103050
CPU
Time
(sec)
Minimum support
c
c
c
SS \Theta
\Theta \Theta \Theta \Theta \Theta
I/O
Time
(sec)
Minimum support
c c
c
c
c
c
SS \Theta
\Theta \Theta \Theta \Theta \Theta \Theta

Figure

3: Execution Times for FS and SS.

Table

3: Meaning of various parameters.
H The height of a traversal tree.
F The number of child nodes, fanout.
N J The number of internal nodes with an internal jump .
Backward weight in probability to its parent node.
in probability to its internal jump.
' A parameter of a Zipf-like distribution.
HxPy x is the height of a tree and
jDj The number of reference paths (size of database).
of forward references for L k .
of candidate k-reference sequences.
of large k-reference sequences.
size of the reference paths.
total number of nodes increases as the height of a tree increases. To make the experiment tractable,
we reduced the fanout to 2 \Gamma 5 for the tree of H20 with the height of 20. This tree contained 616,595
internal nodes and 1,541,693 leaves. In Figure 3, the left graph of each HxPy.D200K represents
the CPU time to find all the large reference sequences, and the right graph shows the I/O time to
find them where the disk I/O time is set to 2 MB/sec and 1 MB buffer is used in main memory.
It can be seen from Figure 3 that algorithm SS in general outperforms FS, and their performance
difference becomes prominent when the I/O cost is taken into account.
To provide more insights into their performance, in addition to Table 2 in Section 3, we have

Table

4 which shows the results by these two methods when In

Table

4, FS scans the database eight times to find all the large reference sequences, whereas SS
only involves three database scans. Note that after initial scans, disk I/O involved by FS and SS
will include both disk read and disk write (i.e., writing the trimmed version of the database back
to the disk). The I/O time for these two methods is shown in Figure 4. Considering both CPU
and I/O times, the total execution time of FS is 143.94 seconds, and that of SS is 100.89 seconds.
Note that the execution time ratio for FS to SS is 0.70 in this case, which is slightly better than
the one associated with Table 2.

Figure

5 shows scale-up experiments, where both the CPU and I/O times of each method increase
linearly as the database size increases. For this experiment, the traversal tree has 10 levels,
the fanout of internal nodes is between 4 and 7, and the minimum support is set to 0.75%. It can
be seen that SS consistently outperforms FS as the database size increases.

Table

4: Number of large reference sequences and execution times for H20P20.
Algorithm FS
Algorithm SS
SS skips database scans for k=2,4,5,6,7
I/O
time
(second)
FS SS

Figure

4: I/O cost for FS and SS in each pass.
200K 400K 600K 800K 1000K
Execution
Time
(sec)
Database size
c
c
c
c
c
SS(cpu) \Theta
\Theta
\Theta
\Theta
\Theta
\Theta

Figure

5: Execution time of FS and SS when database size increases.
4.3 Sensitivity Analysis
Since algorithm SS in general outperforms FS, without loss of generality, we shall conduct in this
section the sensitivity analysis on various parameters for algorithm SS. Performance evaluation was
carried out under the condition that the database size is 200,000, the average size of traversal paths
is 10, i.e., jP and the minimum support is 0.75%.

Figure

6 shows the number of large reference sequences when the probability to backward at an
internal node, p 0 , varies from 0.1 to 0.5. As the probability increases, the number of large reference
sequences decreases because the possibility of having forward traveling becomes smaller. Figure 7
shows the number of large reference sequences when the number of child nodes of internal nodes,
i.e., fanout F , varies. The three corresponding traversal trees all have the same height 8. The tree
consists of 483 internal nodes and 1,267 leaf nodes. The tree for the second bar
consists of 11,377 internal nodes and 62,674 leaf nodes, and the one for the third bar consists of
74,632 internal nodes and 634,538 leaf nodes. The results show that the number of large reference
sequences decreases as the degree of fanout increases, because with a larger fanout the traversal
paths are more likely to be dispersed to several branches, thus resulting in fewer large reference
sequences. Clearly, when the large reference sequences decreases, the execution time to find them
p0=0.1 p0=0.2 p0=0.3 p0=0.4 p0=0.52060100Number
of
large
reference
sequences

Figure

Number of large reference sequences when backward weight p 0 is varied.
also decreases.

Figure

8 gives the number of large reference sequences when the probability of traveling to each
child node from an internal node is determined from a Zipf-like distribution. Different values of
parameter ' for the Zipf-like distribution are considered. The Zipf-like distribution of branching
probabilities to child nodes is generated as follows. The probability p i that the i-th child node
is accessed by a traversal path is
normalization
constant and n is the number of child nodes at an internal node. After we get each p i , it is then
normalized so that
as in Section 4.1. Setting the parameter
to the pure Zipf distribution, which is highly skewed, whereas corresponds to the uniform
distribution. The results show that the number of large reference sequences increases when the
corresponding probabilities are more skewed.

Table

5 shows the performance results of SS when the number of internal nodes with internal
jumps, N J , varies from 3% to 27 % of the total internal nodes. The number of large reference
sequences decreases slightly as N J increases, meaning that it is less likely to have large reference
F (2 to 4) F (5 to to 11)100300500Number
of
large
reference
sequences

Figure

7: Number of large reference sequences when the fanout F is varied.
Degree of skew
Number
of
large
reference
sequences

Figure

8: Number of large reference sequences when parameter ' of a Zipf-like distribution is varied.

Table

5: Number of large reference sequences when the percentage of internal jumps N J is varied.
9

Table

Number of large reference sequences when the height of a traversal tree H is varied.
sequences when we have more jumps in traversal paths. It is noted that performance of SS is less
sensitive to this parameter than to others.

Table

6 shows results of SS when the height of a traversal tree varies. The fanout is between 2
and 5. As the height increases, the numbers of internal nodes and leaf nodes increase exponentially.
The height of a traversal tree is increased from 3 to 20, As the height of a traversal tree increases,
the number of candidate nodes for L 1 increases and the execution time to find L 1 thus increases.
On the other hand, jL decreases as the height of the tree increases since the average visit to each
node decreases. The number of large reference sequences slightly decreases, for 1 - k - 3, when
the height of the tree increases from 5 to 20.
5 Conclusion
In this paper, we have explored a new data mining capability which involves mining traversal
patterns in an information providing environment where documents or objects are linked together
to facilitate interactive access. Our solution procedure consisted of two steps. First, we derived
algorithm MF to convert the original sequence of log data into a set of maximal forward references.
By doing so, we filtered out the effect of some backward references and concentrated on mining
meaningful user access sequences. Second, we developed algorithms to determine large reference
sequences from the maximal forward references obtained. Two algorithms were devised for determining
large reference sequences: one was based on some hashing and pruning techniques, and the
other was further improved with the option of determining large reference sequences in batch so
as to reduce the number of database scans required. Performance of these two methods has been
comparatively analyzed. It is shown that the option of selective scan is very advantageous and algorithm
SS thus in general outperformed algorithm FS. Sensitivity analysis on various parameters
was conducted.

Acknowledgements

M.-S. Chen is in part supported by National Science Council, Project No. NSC 86-2621-E-002-
023-T, Taiwan, ROC. J. S. Park is supported by the Grants for Professors of Sungshin Women's
University in 1997, Korea.



--R

Efficient Similarity Search in Sequence Databases.
An Interval Classifier for Database Mining Applications.
Mining Association Rules between Sets of Items in Large Databases.
Fast Algorithms for Mining Association Rules in Large Databases.
Mining Sequential Patterns.
Knowledge Mining by Imprecise Querying: A Classification-Based Approach
Hypertext Transfer Protocol-HTTP/1.0
Backtracking in a Multiple-Window Hypertext Environment
Browsing in Hypertext: A Cognitive Study.
Characterizing browsing strategies in the world-wide web
The World Wide Web Unleashed.

Discovery of Multiple-Level Association Rules from Large Databases
Efficient and Effective Clustering Methods for Spatial Data Mining.
An Effective Hash Based Algorithm for Mining Association Rules.
Analysis and Presentation of Strong Rules.
Induction of Decision Trees.
Personal communication
Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results.
--TR

--CTR
D. Avramouli , J. Garofalakis , D. J. Kavvadias , C. Makris , Y. Panagis , E. Sakkopoulos, Popular web hot spots identification and visualization, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
Holmquist , N. Hari Narayanan, Tightly coupling authoring and evaluation in an integrated tool to support iterative design of interactive hypermedia educational manuals, Proceedings of the conference on Designing interactive systems: processes, practices, methods, and techniques, p.155-164, August 17-19, 2000, New York City, New York, United States
Wenwu Lou , Hongjun Lu, Efficient prediction of web accesses on a proxy server, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
Hua-Fu Li , Suh-Yin Lee , Man-Kwan Shan, On mining webclick streams for path traversal patterns, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA
Jian-Chih Ou , Chang-Hung Lee , Ming-Syan Chen, Web log mining with adaptive support thresholds, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
Alexandros Nanopoulos , Yannis Manolopoulos , Maciej Zakrzewicz , Tadeusz Morzy, Indexing web access-logs for pattern queries, Proceedings of the 4th international workshop on Web information and data management, November 08-08, 2002, McLean, Virginia, USA
Mao Chen , Andrea S. LaPaugh , Jaswinder Pal Singh, Predicting category accesses for a user in a structured information space, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland
Tiffany Y. Tang , Gordon McCalla, Student modeling for a web-based learning environment: a data mining approach, Eighteenth national conference on Artificial intelligence, p.967-968, July 28-August 01, 2002, Edmonton, Alberta, Canada
Kun-Ta Chuang , Ming-Syan Chen, Frequent pattern discovery with memory constraint, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
Hai Zhuge , Jie Liu, A fuzzy collaborative assessment approach for knowledge grid, Future Generation Computer Systems, v.20 n.1, p.101-111, January 2004
Brenda F. Miles , Vir V. Phoha, The bipartite clique: a topological paradigm for WWWeb user search customization, Proceedings of the 43rd annual southeast regional conference, March 18-20, 2005, Kennesaw, Georgia
Ajumobi Udechukwu , Ken Barker , Reda Alhajj, A framework for representing navigational patterns as full temporal objects, ACM SIGecom Exchanges, v.5 n.2, p.23-33, November, 2004
Wen-Chih Peng , Ming-Syan Chen, Shared Data Allocation in a Mobile Computing System: Exploring Local and Global Optimization, IEEE Transactions on Parallel and Distributed Systems, v.16 n.4, p.374-384, April 2005
Minos N. Garofalakis , Rajeev Rastogi , Kyuseok Shim, SPIRIT: Sequential Pattern Mining with Regular Expression Constraints, Proceedings of the 25th International Conference on Very Large Data Bases, p.223-234, September 07-10, 1999
Tzung-Shi Chen , Shih-Chun Hsu, Mining frequent tree-like patterns in large datasets, Data & Knowledge Engineering, v.62 n.1, p.65-83, July, 2007
Yunjuan Xie , Vir V. Phoha, Web user clustering from access log using belief function, Proceedings of the 1st international conference on Knowledge capture, October 22-23, 2001, Victoria, British Columbia, Canada
Tseng , Cing-Fu Tsui, An efficient method for mining associated service patterns in mobile web environments, Proceedings of the ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
Cheng-Ru Lin , Chang-Hung Lee , Ming-Syan Chen , Philip S. Yu, Distributed data mining in a chain store database of short transactions, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Anindya Datta , Kaushik Dutta , Helen Thomas , Debra VanderMeer , Krithi Ramamritham, Accelerating Dynamic Web Content Generation, IEEE Internet Computing, v.6 n.5, p.27-36, September 2002
Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, Complete Mining of Frequent Patterns from Graphs: Mining Graph Data, Machine Learning, v.50 n.3, p.321-354, March
Chang-Hung Lee , Cheng-Ru Lin , Ming-Syan Chen, Sliding window filtering: an efficient method for incremental mining on a time-variant database., Information Systems, v.30 n.3, p.227-244, May 2005
M. Garofalakis , R. Rastogi , K. Shim, Mining Sequential Patterns with Regular Expression Constraints, IEEE Transactions on Knowledge and Data Engineering, v.14 n.3, p.530-552, May 2002
Karuna P. Joshi , Anupam Joshi , Yelena Yesha, On Using a Warehouse to Analyze Web Logs, Distributed and Parallel Databases, v.13 n.2, p.161-180, March
Qinbao Song , Martin Shepperd, Mining web browsing patterns for E-commerce, Computers in Industry, v.57 n.7, p.622-630, September 2006
Chin-Chen Chang , Chih-Yang Lin , Henry Chou, Perfect hashing schemes for mining traversal patterns, Fundamenta Informaticae, v.70 n.3, p.185-202, April 2006
Alexander Mikroyannidis , Babis Theodoulidis, A Theoretical Framework and an Implementation Architecture for Self Adaptive Web Sites, Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence, p.558-561, September 20-24, 2004
Roderick L. Lee, Web mining: creating structure out of chaos, Managing data mining technologies in organizations: techniques and applications, Idea Group Publishing, Hershey, PA,
Yen-Liang Chen , Ya-Han Hu, Constraint-based sequential pattern mining: the consideration of recency and compactness, Decision Support Systems, v.42 n.2, p.1203-1215, November 2006
Wen-Chih Peng , Ming-Syan Chen, Developing Data Allocation Schemes by Incremental Mining of User Moving Patterns in a Mobile Computing System, IEEE Transactions on Knowledge and Data Engineering, v.15 n.1, p.70-85, January
Alexandros Nanopoulos , Yannis Manolopoulos, Efficient similarity search for market basket data, The VLDB Journal  The International Journal on Very Large Data Bases, v.11 n.2, p.138-152, October 2002
Minos Garofalakis , Rajeev Rastogi, Scalable data mining with model constraints, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.39-48, Dec. 2000
Kamal Ali , Steven P. Ketchpel, Golden Path Analyzer: using divide-and-conquer to cluster Web clickstreams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C.
Shao-Shin Hung , Ting-Chia Kuo , Damon Shing-Min Liu, An Efficient Mining and Clustering Algorithm for Interactive Walk-Through Traversal Patterns, Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence, p.356-362, September 20-24, 2004
Qiankun Zhao , Sourav S. Bhowmick , Le Gruenwald, WAM-Miner: in the search of web access motifs from historical web log data, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
Chang-Hung Lee , Cheng-Ru Lin , Ming-Syan Chen, Sliding-window filtering: an efficient algorithm for incremental mining, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
Jun Wook Lee , Ok Hyun Paek , Keun Ho Ryu, Temporal moving pattern mining for location-based service, Journal of Systems and Software, v.73 n.3, p.481-490, November-December 2004
Yi-Hung Wu , Arbee L.  P. Chen, Prediction of Web Page Accesses by Proxy Server Log, World Wide Web, v.5 n.1, p.67-88, 2002
Huang , Fuchun Peng , Aijun An , Dale Schuurmans, Dynamic web log session identification with statistical language models, Journal of the American Society for Information Science and Technology, v.55 n.14, p.1290-1303, December 2004
Weiyang Lin , Sergio A. Alvarez , Carolina Ruiz, Efficient Adaptive-Support Association Rule Mining for Recommender Systems, Data Mining and Knowledge Discovery, v.6 n.1, p.83-105, January 2002
Zhixiang Chen , Ada Wai-Chee Fu , Frank Chi-Hung Tong, Optimal Algorithms for Finding User Access Sessions from Very Large Web Logs, World Wide Web, v.6 n.3, p.259-279, September
Ali Amiri, Dare to share: Protecting sensitive knowledge with data sanitization, Decision Support Systems, v.43 n.1, p.181-191, February, 2007
Igor Cadez , David Heckerman , Christopher Meek , Padhraic Smyth , Steven White, Model-Based Clustering and Visualization of Navigation Patterns on a Web Site, Data Mining and Knowledge Discovery, v.7 n.4, p.399-424, October
Jos Borges , Mark Levene, A fine grained heuristic to capture web navigation patterns, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.40-50, June, 2000
Yen-Liang Chen , Shih-Sheng Chen , Ping-Yu Hsu, Mining hybrid sequential patterns and sequential rules, Information Systems, v.27 n.5, p.345-362, July 2002
George Pallis , Lefteris Angelis , Athena Vakali, Validation and interpretation of Web users' sessions clusters, Information Processing and Management: an International Journal, v.43 n.5, p.1348-1367, September, 2007
Wei-Guang Teng , Cheng-Yue Chang , Ming-Syan Chen, Integrating Web Caching and Web Prefetching in Client-Side Proxies, IEEE Transactions on Parallel and Distributed Systems, v.16 n.5, p.444-455, May 2005
single-pass mining of path traversal patterns over streaming web click-sequences, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1474-1487, 14 July 2006
Jan-Ming Ho, Entropy-based link analysis for mining web informative structures, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
Shao-Shin Hung , Damon Shing-Min Liu, Efficient reduction of access latency through object correlations in virtual environments, EURASIP Journal on Applied Signal Processing, v.2007 n.1, p.178-178, 1 January 2007
Alexandros Nanopoulos , Dimitrios Katsaros , Yannis Manolopoulos, A Data Mining Algorithm for Generalized Web Prefetching, IEEE Transactions on Knowledge and Data Engineering, v.15 n.5, p.1155-1169, September
Holmquist , N. Hari Narayanan, An integrated architecture for tightly coupled design and evaluation of educational multimedia, Information SciencesInformatics and Computer Science: An International Journal, v.140 n.1, p.127-152, January 2002
Karuna P. Joshi , Anupam Joshi , Yelena Yesha , Raghu Krishnapuram, Warehousing and mining Web logs, Proceedings of the 2nd international workshop on Web information and data management, p.63-68, November 02-06, 1999, Kansas City, Missouri, United States
Hung-Yu Kao , Shian-Hua Lin , Jan-Ming Ho , Ming-Syan Chen, Mining Web Informative Structures and Contents Based on Entropy Analysis, IEEE Transactions on Knowledge and Data Engineering, v.16 n.1, p.41-55, January 2004
Pranam Kolari , Anupam Joshi, Web Mining: Research and Practice, Computing in Science and Engineering, v.6 n.4, p.49-53, July 2004
Anthony J. T. Lee , Yao-Te Wang, Efficient data mining for calling path patterns in GSM networks, Information Systems, v.28 n.8, p.929-948, December
Jose M. Pea, Intelligent Web mining, Intelligent exploration of the web, Physica-Verlag GmbH, Heidelberg, Germany,
data mining;performance analysis;distributed information system;World Wide Web;traversal patterns