On mining webclick streams for path traversal patterns

ABSTRACT

Mining user access patterns from a continuous stream of Web-clicks presents new challenges over traditional Web usage mining in a large static Web-click database. Modeling user access patterns as maximal forward references, we present a single-pass algorithm StreamPath for online discovering frequent path traversal patterns from an extended prefix tree-based data structure which stores the compressed and essential information about user's moving histories in the stream. Theoretical analysis and performance evaluation show that the space requirement of StreamPath is limited to a logarithmic boundary, and the execution time, compared with previous multiple-pass algorithms [2], is fast.

REFERENCES

• 1: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 2: Ming-Syan Chen , Jong Soo Park , Philip S. Yu, Efficient Data Mining for Path Traversal Patterns, IEEE Transactions on Knowledge and Data Engineering, v.10 n.2, p.209-221, March 1998 [doi>10.1109/69.683753]
• 3: Jiawei Han , Jian Pei , Yiwen Yin , Runying Mao, Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach, Data Mining and Knowledge Discovery, v.8 n.1, p.53-87, January 2004 [doi>10.1023/B:DAMI.0000005258.31418.83]
• 4: Richard M. Karp , Scott Shenker , Christos H. Papadimitriou, A simple algorithm for finding frequent elements in streams and bags, ACM Transactions on Database Systems (TODS), v.28 n.1, p.51-55, March 2003 [doi>10.1145/762471.762473]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Performance

Keywords:
data stream mining, path traversal patterns, web-click streams