Why we search: visualizing and predicting user behavior

ABSTRACT

The aggregation and comparison of behavioral patterns on the WWW represent a tremendous opportunity for understanding past behaviors and predicting future behaviors. In this paper, we take a first step at achieving this goal. We present a large scale study correlating the behaviors of Internet users on multiple systems ranging in size from 27 million queries to 14 million blog posts to 20,000 news articles. We formalize a model for events in these time-varying datasets and study their correlation. We have created an interface for analyzing the datasets, which includes a novel visual artifact, the DTWRadar, for summarizing differences between time series. Using our tool we identify a number of behavioral properties that allow us to understand the predictive power of patterns of use.

REFERENCES

• 1: Aizen, J., D. Huttenlocher, J. Kleinberg, and A. Novak, "Traffic-Based Feedback on the Web," PNAS, Suppl. 1: 5254--5260, Apr. 6, 2004.
• 2: Allan, J., J. Carbonell, G. Doddington, J. Yamron, Y. Yang, "Topic Detection and Tracking Pilot Study Final Report," Proc. of the DARPA Broadcast News Transcription and Understanding Workshop, Feb., 1998.
• 3: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 4: Steve Chien , Nicole Immorlica, Semantic similarity between search engine queries using temporal correlation, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060752]
• 5: Evgeniy Gabrilovich , Susan Dumais , Eric Horvitz, Newsjunkie: providing personalized newsfeeds via analysis of information novelty, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988738]
• 6: Daniel Gruhl , R. Guha , Ravi Kumar , Jasmine Novak , Andrew Tomkins, The predictive power of online chatter, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081883]
• 7: Susan Havre , Elizabeth Hetzler , Paul Whitney , Lucy Nowell, ThemeRiver: Visualizing Thematic Changes in Large Document Collections, IEEE Transactions on Visualization and Computer Graphics, v.8 n.1, p.9-20, January 2002 [doi>10.1109/2945.981848]
• 8: Eamonn Keogh , Jessica Lin , Ada Fu, HOT SAX: Efficiently Finding the Most Unusual Time Series Subsequence, Proceedings of the Fifth IEEE International Conference on Data Mining, p.226-233, November 27-30, 2005 [doi>10.1109/ICDM.2005.79]
• 9: Keogh, E.J., and M.J. Pazzani, "Derivative Dynamic Time Warping," SDM '01, Chicago, Apr. 5-7, 2001.
• 10: 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]
• 11: Kleinberg, J., "Temporal Dynamics of On-Line Information Streams," In Data Stream Management: Processing High-Speed Data Streams, M. Garofalakis, J. Gehrke, R. Rastogi, eds., Springer, 2006.
• 12: Lavrenko, V., M. Schmill, D. Lawrie, and P. Ogilvie, D. Jensen and J. Allen, "Mining of Concurrent Text and Time Series," Workshop on Text Mining, KDD '00, Boston, MA. Aug. 20, 2000.
• 13: Jessica Lin , Eamonn Keogh , Stefano Lonardi, Visualizing and discovering non-trivial patterns in large time series databases, Information Visualization, v.4 n.2, p.61-82, July 2005 [doi>10.1057/palgrave.ivs.9500089]
• 14: Martzoukou, K., "A review of Web information seeking research: considerations of method and foci of interest," Information Research, 10(2), paper 215, 2004.
• 15: Microsoft Live Labs, "Accelerating Search in Academic Research," 2006.
• 16: Murray, G. C., J. Lin, and A. Chowdhury, "Identification of User Sessions with Hierarchical Agglomerative Clustering," ASIS&T'06, Austin, TX, Nov. 3-8, 2006.
• 17: Myers, C.S., and L.R. Rabiner, "A Comparative Study of Several Dynamic Time-Warping Algorithms for Connected Word Recognition," The Bell System Tech. J., 60(7):1389--1408, September, 191.
• 18: Nielsen BuzzMetrics, ICWSM Conference dataset, http://www.icwsm.org/data.html
• 19: Greg Pass , Abdur Chowdhury , Cayley Torgeson, A picture of search, Proceedings of the 1st international conference on Scalable information systems, p.1-es, May 30-June 01, 2006, Hong Kong [doi>10.1145/1146847.1146848]
• 20: Sakoe, H., and S. Chiba, "Dynamic Programming Algorithm Optimization for Spoken Word Recognition," IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-26(1):43--49, 1978.
• 21: Jaime Teevan , Eytan Adar , Rosie Jones , Michael Potts, History repeats itself: repeat queries in Yahoo's logs, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148326]
• 22: Edward R. Tufte, Beautiful Evidence, Graphis Pr, 2006
• 23: Jarke J. Van Wijk , Edward R. Van Selow, Cluster and Calendar Based Visualization of Time Series Data, Proceedings of the 1999 IEEE Symposium on Information Visualization, p.4, October 24-29, 1999
• 24: 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]
• 25: Marc Weber , Marc Alexa , Wolfgang Müller, Visualizing Time-Series on Spirals, Proceedings of the IEEE Symposium on Information Visualization 2001 (INFOVIS'01), p.7, October 22-23, 2001
• 26: Query clustering using user logs, ACM Transactions on Information Systems (TOIS), v.20 n.1, p.59-81, January 2002 [doi>10.1145/503104.503108]
• 27: Witkin, A. P. "Scale-space filtering", IJCAI '83, Karlsruche, Germany, Aug. 8-12, 1983.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Human Factors, Measurement

Keywords:
DTW, data mining, user behavior, visualization