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

Patent 5668988 Issued on September 16, 1997. Estimated Expiration Date:

September 8, 2015. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Bubble domain relational data base system
Patent #: 4221003
Issued on: 09/02/1980
Inventor: Chang , et al.

System for automatically and transparently mapping rules and objects from a stable storage database management system within a forward chaining or backward chaining inference cycle
Patent #: 5136523
Issued on: 08/04/1992
Inventor: Landers

Electronic dictionary system with automatic extraction and recognition of letter pattern series to speed up the dictionary lookup operation
Patent #: 5241674
Issued on: 08/31/1993
Inventor: Kuorsawa, et al.

Data base system
Patent #: 5345544
Issued on: 09/06/1994
Inventor: Iwasaki, et al.

Method and system for retrieving time-series information
Patent #: 5412769
Issued on: 05/02/1995
Inventor: Maruoka, et al.

Rhythm creating system for creating a rhythm pattern from specifying input data
Patent #: 5486646
Issued on: 01/23/1996
Inventor: Yamashita, et al.

Method for finding a reference token sequence in an original token string within a database of token strings using appended non-contiguous substrings Patent #: 5577249
Issued on: 11/19/1996
Inventor: Califano

Inventors

Application

No. 525891 filed on 09/08/1995

US Classes:

707/101, Manipulating data structure (e.g., compression, compaction, compilation)707/1, DATABASE OR FILE ACCESSING707/2, Access augmentation or optimizing707/3, Query processing (i.e., searching)707/6, Pattern matching access707/100DATABASE SCHEMA OR DATA STRUCTURE

Examiners

Primary: Black, Thomas G.
Assistant: Homere, Jean R.

Attorney, Agent or Firm

Jordan; Kevin M.

International Class

G06F 017/30

Abstract

An efficient computer implemented method of mining path traversal patterns in a communications network. The method of the present invention comprises two steps. A method, called MF (standing for maximal forward references), is first used to convert an original sequence of log data into a set of traversal subsequences. Each traversal subsequence represents a maximal forward reference from the starting point of a user access. 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. Accordingly, 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 reference and begin a new 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. Second, methods are developed 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 a sufficient number of times in the database to exceed a predetermined threshold.

Other References

Chen et al., "Data Mining for Path Traversal Patterns in a Web Environment", IEEE, Proceedings of the 16th ICDCS, 1996, pp. 385-392
Agrawal et al., "Fast Algorithms for Mining Association Rules in Large Databases", IEEE, Proceedings of the 20th IC on VLDB, Sep. 1994, pp. 478-499
Park et al., "An Effective Hash Based Algorithm for Mining Association Rules" Proceedings of ACM Sigmod, May, 1995, pp. 175-186
Agrawal et al, "Efficient Similarity Search in Sequence Databases," Proceedings of the 4th IC on FDOA, Oct. 199