Optimizing hypervideo navigation using a Markov decision process approach

ABSTRACT

Interaction with hypermedia documents is a required feature for new sophisticated yet flexible multimedia applications. This paper presents an innovative adaptive technique to stream hypervideo that takes into account user behaviour. The objective is to optimize hypervideo prefetching in order to reduce the latency caused by the network. This technique is based on a model provided by a Markov Decision Process approach. The problem is solved using two methods: classical stochastic dynamic programming algorithms and reinforcement learning. Experimental results under stochastic network conditions are very promising.

REFERENCES

• 1: MPEG-21, MPEG Group, Multimedia Framework, http://www.cselt.it/mpeg
• 2: B. Trousse, Evaluation of the Prediction Capability of a User behaviour Mining Approach for Adapative Web Sites, Proc. RIAO 2000, 6th Conference on Content-Based Multimedia Information Access, Paris, France, 2000.
• 3: Apple, QuickTimeVR, http://quicktime.apple.com
• 4: Nitin Sawhney , David Balcom , Ian Smith, Authoring and Navigating Video in Space and Time, IEEE MultiMedia, v.4 n.4, p.30-39, October 1997 [doi>10.1109/93.641877]
• 5: J. Tolva, MediaLoom, An Interactive Authoring Tool for HyperVideo, M.S. Project Paper, Georgia Institute of Technology, 1998.
• 6: Ingrid Zukerman , David W. Albrecht, Predictive Statistical Models for User Modeling, User Modeling and User-Adapted Interaction, v.11 n.1-2, p.5-18, 2001 [doi>10.1023/A:1011175525451]
• 7: M. Crovella, P. Barford, The Network Effects of Prefetching, Proc. of Infocom'98, IEEE, April 1998.
• 8: Y. Aumann et al., Predicting Event Sequences: Data Mining for Prefetching Web-pages, Proc. of KDD'98.
• 9: bibliothek ARRAY(0x84778f8) EMAIL::, Resource Prediction and Admission Control for Interactive Video Browsing Scenarios Using Application Semantics, European Research Consortium for Informatics and Mathematics at FHG, 1998
• 10: David W. Albrecht , Ingrid Zukerman , Ann E. Nicholson, Pre-sending Documents on the WWW: A Comparative Study, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1274-1279, July 31-August 06, 1999
• 11: T. Syeda-Mahmood, Learning and Tracking Browsing Behavior of Users using Hidden Markov Models, IBM Make It Easy Conference, 2001.
• 12: Tanveer Syeda-Mahmood , Dulce Ponceleon, Learning video browsing behavior and its application in the generation of video previews, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500161]
• 13: A. Kohrs, B. Merialdo, Creating user-adapted Websites by the use of collaborative filtering, Interacting with Computers, Volume 13, Issue 6, August 2001.
• 14: R. Grigoraş, V. Charvillat, M. Douze, Self-adaptive multimedia content, Proc. ECMCS, September 2001.
• 15: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 16: Dimitri P. Bertsekas , John N. Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, 1996
• 17: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 18: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems

Keywords:
Markov Decision Process, hypermedia, interaction, navigation, optimization, prefetching, reinforcement learning, simulation, streaming, uncertainty