To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.06.055 Byline: Kaushik Dutta (a), Debra VanderMeer (a), Anindya Datta (b)(c), Pinar Keskinocak (d), Krithi Ramamritham (e) Keywords: Data mining; e-Commerce; Graph theory; Applied probability 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, the discovery of critical edge sequences (CESs), which denote frequently traversed sequences in the catalog, is of significant interest. 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 behavior patterns on the site. Using web mining strategies to find CESs turns out to be expensive in both space and time. In this paper, we propose an approximate algorithm to compute the most popular traversal sequences between node pairs in a catalog, which are then used to discover CESs. Our method is both fast and space efficient, providing a vast reduction in both the run time and storage requirements, with minimum impact on accuracy. Author Affiliation: (a) Department of Decision Sciences and Information Systems, Florida International University, Miami, Florida 33199, United States (b) Walking Stick Solutions, 75 Fifth Street NW, Suite 218, Atlanta, Georgia 30308, United States (c) School of Information Systems, Singapore Management University, 80 Stamford Rd, Singapore 178902 (d) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332, United States (e) Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India Article History: Received 23 July 2005; Accepted 30 June 2006 Article Note: (footnote) [star] An early version of this work appeared in the ACM Conference on Electronic Commerce, 2001.