Discovering critical edge sequences in E-commerce catalogs

ABSTRACT

Web sites allow the collection of vast amounts of navigational data -- clickstreams of user traversals through the site. These massive data stores offer the tantalizing possibility of uncovering interesting patterns within the dataset. For e-businesses, always looking for an edge in the hyper-competitive online marketplace, this possibility is of particular interest. Of significant particular interest to e-businesses is the discovery of Critical Edge Sequences (CES), which denote frequently traversed subpaths in the catalog. CESs can be used to improve site performance and site management, increase the effectiveness of advertising on the site, and gather additional knowledge of customer interest patterns on the site.Using traditional graph-based and web mining strategies to find CESs could turn out to be expensive in both space and time. In this paper, we propose a method to compute the most popular paths bewteen node pairs in a catalog, which are then used to discover CESs. Our method is both space-efficient and accurate, providing a vast reduction in the storage requirement with a minimum impact on accuracy. This algorithm, executed off-line in batch mode, is also practical with respect to running time. As a variant of single-source shortest-path, it runs in log linear time.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 4: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 5: Roberto J. Bayardo, Jr. , Rakesh Agrawal, Mining the most interesting rules, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.145-154, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312219]
• 6: Data mining for path traversal patterns in a web environment, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.385, May 27-30, 1996
• 7: Introduction to algorithms, MIT Press, Cambridge, MA, 2001
• 8: A. Datta, D. VanderMeer, K. Ramamritham, and S. Navathe. Toward a comprehensive model of the content and structure of, and user interaction over, a web site. In Proceedings of the VLDB Workshop on Technologies for E-Services, Cairo, Egypt, September 2000.
• 9: E. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959.
• 10: K. Dutta, D. VanderMeer, A. Datta, and K. Ramamritham. Discovering critical edge sequences in e-commerce catalogs. Technical report, Chutney Technologies Technical Report TR2001-15, 2001.
• 11: Daniela Florescu , Alon Y. Levy , Dan Suciu , Khaled Yagoub, Optimization of Run-time Management of Data Intensive Web-sites, Proceedings of the 25th International Conference on Very Large Data Bases, p.627-638, September 07-10, 1999
• 12: Flip Korn , Alexandros Labrinidis , Yannis Kotidis , Christos Faloutsos, Quantifiable data mining using ratio rules, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.254-266, February 2000 [doi>10.1007/s007780050007]
• 13: B. Mosbasher, N. Jain, E. Han, and J. Srivastava. Web mining: Pattern discovery from world wide web transactions. Technical Report 96-050, University of Minnesota, Dept. of Computer Science, Minneapolis, 1996.
• 14: J. Pitkow and P. Priolli. Mining longest repeating subsequences to predict world wide web surfing. In Proceedings of USITS'99: The 2nd USENIX Symposium on Internet Technologies and Systems, Boulder, Colorado, October 1999.
• 15: D. Simpson. Corral your storage management costs. Datamation, pages 88-93, April 1997.
• 16: M. Spiliopoulou, L. Faulstich, and K. Winkler. A data miner analyzing the navigaitional behavior of web users. In International Conference ofACAI'99: Workshop on Machine Learning in User Modelling, 1999.
• 17: Ramakrishnan Srikant , Rakesh Agrawal, Mining Sequential Patterns: Generalizations and Performance Improvements, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.3-17, March 25-29, 1996
• 18: M. Zaki, N. Lesh, and M. Ogihara. Planmine: Sequence mining for plan failures. In Proceedings of the 4th Intl. Conference on Knowledge Discovery and Data Mining, pages 369-373, 1998.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Performance

Keywords:
accuracy, approximation, critical edge sequence, web site performance, web usage analysis