Method for mining path traversal patterns in a web environment by converting an original log sequence into a set of traversal sub-sequences

A computer program product comprising:

• a computer usable medium having computer readable program code means embodied therein for determining frequent node traversal patterns in a communications network coupled to a computer which includes a memory and a trace collector for collecting node traversal sequences, said computer readable program code means comprising:
• computer readable program code means for causing the computer to effect collecting and storing the node traversal sequences, each node traversal sequence including an end user identifier, a source node and a destination node;
• computer readable program code means for causing the computer to effect sorting the node traversal sequences by end user identifier into a series of time-ordered pairs, responsive to said computer readable program code means for causing the computer to effect said collecting and storing;
• computer readable program code means for causing the computer to effect determining a set of maximal forward references from said series of time-ordered pairs;
• and
• computer readable program code means for causing the computer to effect determining a set of large reference sequences from said set of maximal forward references, a large reference sequences being a consecutive subsequence of said maximal forward references which occurs in excess of a predetermined threshold.

A program storage device readable by a computer tangibly embodying a program of instructions executable by said computer to perform method steps for determining frequent node traversal patterns in a communications network coupled to a computer which includes a memory and a trace collector for collecting node traversal sequences, said method steps comprising:

• collecting and storing the node traversal sequences, each node traversal sequence including an end user identifier, a source node and a destination node;
• sorting the node traversal sequences by said end user identifier into a series of time-ordered pairs, responsive to said steps of collecting and storing;
• determining a set of maximal forward references from said series of time-ordered pairs;
• and
• determining a set of large reference sequences from said set of maximal forward references, a large reference sequence being a consecutive subsequence of said maximal forward references which occurs in excess of a predetermined threshold.

A program storage device readable by a computer tangibly embodying a program of instructions executable by said computer to perform method steps for determining frequent node traversal patterns in a communications network coupled to a computer which includes a memory and a trace collector for collecting node traversal sequences, said method steps comprising:

• collecting and storing the node traversal sequences, each node traversal sequence including an end user identifier, a source node and a destination node;
• sorting the node traversal sequences by said end user identifier into a series of time-ordered pairs, responsive to said steps of collecting and storing;
• determining a set of maximal forward references from said series of time-ordered pairs;
• determining a set of large reference sequences from said set of maximal forward references, a large reference sequence being a consecutive subsequence of said maximal forward references which occurs in excess of a predetermined threshold;
• constructing a set of maximal reference sequences from said large reference sequences, wherein a maximal reference sequence is not a subset of another maximal reference sequence;
• and
• caching said maximal reference sequences for reducing an access time to the frequent node traversal pattern associated with said maximal reference sequence.