Published Articles >> Table of Contents >> Abstract

Seventh International Database Engineering and Applications Symposium (IDEAS'03)   p. 117
Linear and Sublinear Time Algorithms for Mining Frequent Traversal Path Patterns from Very Large Web Logs
Zhixiang Chen, University of Texas-Pan American
Richard H. Fowler, University of Texas-Pan American
Ada Wai-Chee Fu, Chinese University of Hong Kong
Chunyue Wang, University of Texas-Pan American

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IDEAS.2003.1214918
Send link to a friend

Abstract
This paper aims for designing algorithms for the problem of mining frequent traversal path patterns from very large Web logs with best possible efficiency. We devise two algorithms for this problem with the help of fast construction of "shallow" generalized suffix trees over a very large alphabet. These two algorithms have respectively provable linear time and sublinear complexity, and their performance is analyzed in comparison with the two apriori-like algorithms in [4] and the well-known Ukkonen algorithm for on-line suffix tree construction [13]. It is shown that these two algorithms are substantially efficient than the two apriori-like algorithms and the Ukkonen algorithm. The linear time algorithm has optimal performance in theory, while the sublinear time algorithm has better empirical performance.
Back to Top Additional Information
Citation:  Zhixiang Chen, Richard H. Fowler, Ada Wai-Chee Fu, Chunyue Wang, "Linear and Sublinear Time Algorithms for Mining Frequent Traversal Path Patterns from Very Large Web Logs," ideas, p. 117,  Seventh International Database Engineering and Applications Symposium (IDEAS'03),  2003