Optimizing web traffic via the media scheduling problem

ABSTRACT

Website traffic varies through time in consistent and predictable ways, with highest traffic in the middle of the day. When providing media content to visitors, it is important to present repeat visitors with new content so that they keep coming back. In this paper we present an algorithm to balance the need to keep a website fresh with new content with the desire to present the best content to the most visitors at times of peak traffic. We formulate this as the media scheduling problem, where we attempt to maximize total clicks, given the overall traffic pattern and the time varying clickthrough rates of available media content. We present an efficient algorithm to perform this scheduling under certain conditions and apply this algorithm to real data obtained from server logs, showing evidence of significant improvements in traffic from our algorithmic schedules. Finally, we analyze the click data, presenting models for why and how the clickthrough rate for new content declines as it ages.

REFERENCES

• 1: D. Agarwal, B. Chen, P. Elango, N. Motgi, S.-T. Park, R. Ramakrishnan, S. Roy, and J. Zachariah. Online models for content optimization. In Proc. 21st NIPS, 2008.
• 2: A.-L. Barabási. The origin of bursts and heavy tails in human dynamics. Nature, 435:207--211, 2005.
• 3: Peter Brucker, Scheduling Algorithms, Springer Publishing Company, Incorporated, 2007
• 4: Abhinandan S. Das , Mayur Datar , Ashutosh Garg , Shyam Rajaram, Google news personalization: scalable online collaborative filtering, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242610]
• 5: Anirban Dasgupta , Arpita Ghosh , Hamid Nazerzadeh , Prabhakar Raghavan, Online story scheduling in web advertising, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1275-1284, January 04-06, 2009, New York, New York
• 6: A. Johansen. Response time of internauts. Physica A, 296(3-4):539--546, 2000.
• 7: A. Johansen. Probing human response times. Physica A, 338(1-2):286--291, 2004.
• 8: A. Johansen and D. Sornette. Download relaxation dynamics in the WWW following newspaper publication of URL. Physica A, 276(1-2):338--345, 2000.
• 9: Joseph Leung , Laurie Kelly , James H. Anderson, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, Inc., Boca Raton, FL, 2004
• 10: J. G. Oliveira and A.-L. Barabasi. Human dynamics: Darwin and Einstein correspondence patterns. Nature, 437:1251, 2005.
• 11: Ramakrishnan Srikant , Yinghui Yang, Mining web logs to improve website organization, Proceedings of the 10th international conference on World Wide Web, p.430-437, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372097]
• 12: G. Szabo and B. A. Huberman. Predicting the popularity of online content. Technical Report abs/0811.0405, CoRR, 2008.
• 13: A. Vazquez. Exact results for the barabásic model of human dynamics. Phy. Rev. Let., 95:248701, 2005.
• 14: A. Vázquez, J. G. Oliveira, Z. Dezsö, K.-I. Goh, I. Kondor, and A.-L. Barabási. Modeling bursts and heavy tails in human dynamics. Phy. Rev. E, 73(6), 2006.
• 15: F. Wu and B. A. Huberman. Novelty and collective attention. PNAS, 104(45):17599--17601, 2007.
• 16: Fang Wu , Bernardo A. Huberman, Popularity, novelty and attention, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA [doi>10.1145/1386790.1386828]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
human response, media scheduling, user interaction