SearchGen: a synthetic workload generator for scientific literature digital libraries and search engines

ABSTRACT

Due to the popularity of web applications and their heavy usage, it is important to obtain a good understanding of their workloads in order to improve performance of search services. Existing works have typically focused on generic web workloads without putting emphasis on specific domains. In this paper, we analyze the usage logs of CiteSeer, a scientific literature digital library and search engine, to characterize workloads for both robots and users. Essential ingredients that contribute to workloads are proposed. Among them we find the access intervals show high variance, and thus cannot be predicted well with time-series models. On the other hand, client visiting path and semantics can be well captured with probabilistic models and Zipf-law. Based on the findings, we propose SearchGen, a synthetic workload generator to output traces for scientific literature digital libraries and search engines. A comparison between synthetic workloads and actual logged traces suggests that the synthetic workload fits well.

REFERENCES

• 1: Ghaleb Abdulla , Edward A. Fox, Analysis and modeling of world wide web traffic, Virginia Polytechnic Institute and State University, 1998
• 2: C. S. Badue, R. Barbosa, P. Golgher, B. Ribeiro-Neto, and N. Ziviani. Distributed processing of conjunctive queries. In HDIR '05, SIGIR 2005, 2005.
• 3: Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
• 4: L. Bent , M. Rabinovich , G. M. Voelker , Z. Xiao, Characterization of a large web site population with implications for content delivery, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988743]
• 5: J. Beran. Statistics for Long-Memory Processes. Chapman & Hall, New York, NY, 1994.
• 6: B. Berendt, B. Mobasher, M. Spiliopoulou, and J. Wiltshire. Measuring the accuracy of sessionizers for web usage analysis. In Proceedings of the Web Mining Workshop at the 1st SIAM International Conference on Data Mining, Chicago, Illinois, April 2001.
• 7: George Edward Pelham Box , Gwilym Jenkins, Time Series Analysis, Forecasting and Control, Holden-Day, Incorporated, 1990
• 8: S. Chaudhuri, P. Ganesan, and V. R. Narasayya. Primitives for workload summarization and implications for SQL. In VLDB, pages 730--741, 2003.
• 9: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 10: P. Dinda and D. O'Hallaron. An extensible toolkit for resource prediction in distributed systems, 1999.
• 11: C. Lee Giles , Kurt D. Bollacker , Steve Lawrence, CiteSeer: an automatic citation indexing system, Proceedings of the third ACM conference on Digital libraries, p.89-98, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276685]
• 12: Maria E. Gomez , Vicente Santonja, Analysis of Self-Similarity in I/O Workload Using Structural Modeling, Proceedings of the 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.234, March 24-28, 1999
• 13: Terence Kelly , Jeffrey Mogul, Aliasing on the world wide web: prevalence and performance implications, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511484]
• 14: D. E. Knuth. The Art of Computer Programming. Four volumes. Addison-Wesley, 1969.
• 15: Huajing Li , Isaac Councill , Wang-Chien Lee , C. Lee Giles, CiteSeerx: an architecture and web service design for an academic document search engine, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135926]
• 16: Y. Lu, T. Abdelzaher, C. Lu, and G. Tao. An adaptive control framework for QoS guarantees and its application to differentiated caching services, 2002.
• 17: Eren Manavoglu , Dmitry Pavlov , C. Lee Giles, Probabilistic User Behavior Models, Proceedings of the Third IEEE International Conference on Data Mining, p.203, November 19-22, 2003
• 18: R. Sen and M. Hansen. Predicting a web user's next access based on log data. Journal of Computational and Graphical Statistics, 12:143--155(13), 2003.
• 19: Rob Simmonds , Carey Williamson , Russell Bradford , Martin Arlitt , Brian Unger, Web server benchmarking using parallel WAN emulation, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 20: A. Streit. Self-Tuning Job Scheduling Strategies for the Resource Management of HPC Systems and Computational Grids. PhD thesis, Faculty of Computer Science, Electrical Engineering and Mathematics, University Paderborn, 2003.
• 21: Pang-Ning Tan , Vipin Kumar, Discovery of Web Robot Sessions Based on their Navigational Patterns, Data Mining and Knowledge Discovery, v.6 n.1, p.9-35, January 2002 [doi>10.1023/A:1013228602957]
• 22: Nancy Tran , Daniel A. Reed, ARIMA time series modeling and forecasting for adaptive I/O prefetching, Proceedings of the 15th international conference on Supercomputing, p.473-485, June 2001, Sorrento, Italy [doi>10.1145/377792.377905]
• 23: Y. Wang, M. J. Rutherford, A. Carzaniga, and A. L. Wolf. Weevil: a tool to automate experimentation with distributed systems. Technical Report CU-CS-980-04, Department of Computer Science, University of Colorado, Oct. 2004.
• 24: Jianyong Zhang , Anand Sivasubramaniam , Hubertus Franke , Natarajan Gautam , Yanyong Zhang , Shailabh Nagar, Synthesizing Representative I/O Workloads for TPC-H, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.142, February 14-18, 2004 [doi>10.1109/HPCA.2004.10019]
• 25: Steve Zhang , Ira Cohen , Julie Symons , Armando Fox, Ensembles of Models for Automated Diagnosis of System Performance Problems, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.644-653, June 28-July 01, 2005 [doi>10.1109/DSN.2005.44]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.6 Library Automation
          Subjects: Large text archives

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Measurement, Performance, Verification

Keywords:
benchmark, modeling, synthetic workload