Scalable and near real-time burst detection from eCommerce queries

ABSTRACT

In large scale online systems like Search, eCommerce, or social network applications, user queries represent an important dimension of activities that can be used to study the impact on the system, and even the business. In this paper, we describe how to detect, characterize and classify bursts in user queries in a large scale eCommerce system. We build upon the approaches discussed in KDD 2002 "Bursty and Hierarchical Structure in Streams" [3] and apply them to a high volume industrial context. We describe how to identify bursts on a near real-time basis, classify them, and apply them to build interesting merchandizing applications.

REFERENCES

• 1: Michèle Basseville , Igor V. Nikiforov, Detection of abrupt changes: theory and application, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Chris Curry , Robert L. Grossman , David Locke , Steve Vejcik , Joseph Bugajski, Detecting changes in large data sets of payment card data: a case study, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281303]
• 3: Jon Kleinberg, Bursty and hierarchical structure in streams, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775061]
• 4: Rabiner Lawrence R., A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, Vol 77, No 2, February 1989.
• 5: Aboufadel Edward, Schlicker Steven., Discovering Wavelets. A Wiley-Interscience Publication.
• 6: Hulata Eyal, Segev Ronen, Ben-Jacob Eshel., A method for spike sorting and detection based on wavelet packets and Shannon's mutual information. Journal of Neuroscience Methods 117(2002) 1 -- 12.
• 7: Vlachos Michail, Lin Jessica, Keogh Eamonn, Gunopulos Dimitrios., A Wavelet-Based Anytime Algorithm for K-Means Clustering of Time Series. 3rd SIAM International Conference on Data Mining.
• 8: Yi Jeonghee, Detecting buzz from time-sequenced document streams. 2005 IEEE International Conference Proceedings.
• 9: Xuanhui Wang , ChengXiang Zhai , Xiao Hu , Richard Sproat, Mining correlated bursty topic patterns from coordinated text streams, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281276]
• 10: Micah Dubinko , Ravi Kumar , Joseph Magnani , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, Visualizing tags over time, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135810]
• 11: http://buzz.yahoo.com
• 12: http://www.google.com/trends
• 13: Shaker M. EEG Waves Classifier using Wavelet Transform and Fourier Transform. Intl. Journal of Biomedical Sciences Volume 1, Number 1, 2006.
• 14: Chazal P., Celler B., Reilly R. Using Wavelet Coefficients for the Classification of the Electrocardiogram. Proceedings of World Congress on Medical Physics and Biomedical Engineering, 2000.
• 15: Cruden D., Hu X. The shapes of some mountain peaks in the Canadian Rockies. Earth Surface Processes and Landforms, Volume 24, Issue 13.
• 16: Michail Vlachos , Christopher Meek , Zografoula Vagena , Dimitrios Gunopulos, Identifying similarities, periodicities and bursts for online search queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007586]
• 17: Cyrus Shahabi , Seokkyung Chung , Maytham Safar , George Hajj, 2D TSA-tree: A Wavelet-Based Approach to Improve the Efficiency of Multi-Level Spatial Data Mining, Proceedings of the 13th International Conference on Scientific and Statistical Database Management, p.59-68, July 18-20, 2001
• 18: Tao Li , Qi Li , Shenghuo Zhu , Mitsunori Ogihara, A survey on wavelet applications in data mining, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.49-68, December 2002 [doi>10.1145/772862.772870]
• 19: Kleinberg J. Temporal Dynamics of On-Line Information Streams. Processing High-Speed Data Streams, Springer 06.
• 20: Michael S. Lewicki, Bayesian modeling and classification of neural signals, Neural Computation, v.6 n.5, p.1005-1030, Sept. 1994 [doi>10.1162/neco.1994.6.5.1005]
• 21: Shyang Ho S., Wechsler H. Detecting Changes in Unlabeled Data Streams using Martingale. IJCAI07.
• 22: http://www.woot.com
• 23: http://wordsmith.org/awad/

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms, Design, Experimentation, Measurement

Keywords:
temporal burst-mining, temporal classification, wavelet-based feature extraction