On balancing between transcoding overhead and spatial consumption in content adaptation

ABSTRACT

We propose a method that can find the optimal tradeoff point between transcoding overhead (CPU cost) and storage needed for the various pre-processed content variants (I/O cost). The method selectively pre-adapts a subset of content variants and leaves the generation of the residue to dynamic content adaptation with this pre-adapted subset as an input. We prove bounds regarding the optimality of the algorithm employed. The proposed model creates a collaborative environment across the components of client, proxy and server, based on which we study the distribution of adaptation complexity across these components. We use simulation to verify the projected benefits. The method has been successfully implemented in a trial PDF document content adaptation system.

REFERENCES

• 1: Timothy W. Bickmore , Bill N. Schilit, Digestor: device-independent access to the World Wide Web, Selected papers from the sixth international conference on World Wide Web, p.1075-1082, September 1997, Santa Clara, California, United States
• 2: Susanne Boll , Wolfgang Klas , Jochen Wandel, A cross-media adaptation strategy for multimedia presentations, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.37-46, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319468]
• 3: K. H. Britton , R. Case , A. Citron , R. Floyd , Y. Li , C. Seekamp , B. Topol , K. Tracey, Transcoding: extending e-business to new environments, IBM Systems Journal, v.40 n.1, p.153-178, January 2001
• 4: Valeria Cardellini , Philip S. Yu , Yun-Wu Huang, Collaborative proxy system for distributed Web content transcoding, Proceedings of the ninth international conference on Information and knowledge management, p.520-527, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354861]
• 5: S. Chandra, C.S. Ellis, and A. Vahdat, "Differentiated Multimedia Web Services Using Quality Aware Transcoding", 19th Annual Joint Conference of the IEEE Computer and Communication Societies (INFOCOM 2000), Tel Aviv, Israel, Mar. 2000, pp. 961--969.
• 6: S. Chandra and C.S. Ellis, "JPEG Compression Metric as a Quality Aware Image Transcoding", In 2nd Usenix Symposium on Internet Technologies and Systems (USITS '99), Oct. 1999.
• 7: Exploring Aggregate Effect with Weighted Transcoding Graphs for Efficient Cache Replacement in Transcoding Proxies, Proceedings of the 18th International Conference on Data Engineering, p.383, February 26-March 01, 2002
• 8: Richard Comerford, Handhelds duke it out for the Internet, IEEE Spectrum, v.37 n.8, p.35-41, August, 2000 [doi>10.1109/6.861776]
• 9: Gregory D. Abowd , Anind K. Dey , Peter J. Brown , Nigel Davies , Mark Smith , Pete Steggles, Towards a Better Understanding of Context and Context-Awareness, Proceedings of the 1st international symposium on Handheld and Ubiquitous Computing, p.304-307, September 27-29, 1999, Karlsruhe, Germany
• 10: E-Bay.com, http://www.ebay.com
• 11: A. Fox, I. Goldberg, S. Gribble, D.C. Lee, A. Polito, and E.A. Brewer, "Experience with TopGun Wingman: A Proxy-Based Web Browser for the 3Com PalmPilot", in Proceedings of Middleware '98, Lake District, England, Sept. 1998.
• 12: A. Fox, S.D. Gribble, Y. Chawathe, and E.A. Brewer, "Adapting to network and client variation via On-Demand Distillation", in Proceedings of the 16th Symposium on Operating Systems Principles (SOSP-16), Oct. 1997.
• 13: Richard Han, Factoring a mobile client's effective processing speeed into the image transcoding decision, Proceedings of the 2nd ACM international workshop on Wireless mobile multimedia, p.91-98, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313256.313285]
• 14: R. Han, P. Bhagwat, R. LaMaire, T. Mummert, V. Perret, and J. Rubas, "Dynamic Adaptation in an Image Transcoding Proxy for Mobile Web Browsing", IEEE Personal Comm., Dec. 1998, pp. 8--17.
• 15: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 16: M. Hori, K. Ono, G. Kondoh, and S. Singhal, "Authoring tool for Web content transcoding", in Proceedings of Markup Technologies '99, Philadelphia, PA, 1999, pp. 77--85.
• 17: S. C. Ihde, P.P. Maglio, J. Meyer, and R. Barrett, "Intermediary-based transcoding framework", in Poster Proceedings of the 9th International World Wide Web Conference (WWW9), 2000.
• 18: Z. Lei and N.D. Georganas, "Context-based Media Adaptation in Pervasive Computing", in Proceedings of Can.Conf. on Electr. and Comp. Engg (CCECE 2001), Toronto, May 2001.
• 19: W. Y. Lum , Francis C. M. Lau, A QoS-Sensitive Content Adaptation System for Mobile Computing, Proceedings of the 26th International Computer Software and Applications Conference on Prolonging Software Life: Development and Redevelopment, p.680-688, August 26-19, 2002
• 20: Wai Yip Lum , Francis C. M. Lau, A Context-Aware Decision Engine for Content Adaptation, IEEE Pervasive Computing, v.1 n.3, p.41-49, July 2002 [doi>10.1109/MPRV.2002.1037721]
• 21: W.Y. Lum, F.C.M. Lau, Effective Content Adaptation: Response Time and Transcoding Overhead vs Spatial Consumption, tech. report TR-2002-02, Dept. of Computer Science and Information Systems, The University of Hong Kong, Hong Kong, 2002.
• 22: Anuj Maheshwari , Aashish Sharma , Krithi Ramamritham , Prashant Shenoy, TranSquid: Transcoding and Caching Proxy for Heterogenous E-Commerce Environments, Proceedings of the 12th International Workshop on Research Issues in Data Engineering: Engineering E-Commerce/E-Business Systems (RIDE'02), p.50, February 24-25, 2002
• 23: J.C. Mogul, "Server-Directed Transcoding", Computer Communications 24(2):155-162, Feb. 2001.
• 24: R. Mohan, J.R. Smith, and C.-S. Li, "Adapting multimedia Internet content for universal access", IEEE Trans. Multimedia, vol. 1, no. 1, Mar 1999, , pp. 104--114.
• 25: K. Nagao, "Semantic transcoding: Making the World Wide Web more understandable and usable with external annotations", Proc. Int'l Conf. on Advanced in Infrastructure for Electronic Business, Science, and Education on the Internet, L'Aqila, Italy, July 2000.
• 26: Brian Noble , M. Satyanarayanan , Morgan Price, A Programming Interface for Application-Aware Adaptation in Mobile Computing, Proceedings of the 2nd Symposium on Mobile and Location-Independent Computing, p.57-66, April 10-11, 1995
• 27: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 28: C. Parris, B. Dennis, "Transformation Proxy Support for Thin-Clients", http://citeseer.nj.nec.com/58739.html
• 29: Amit Shukla , Prasad Deshpande , Jeffrey F. Naughton, Materialized View Selection for Multidimensional Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.488-499, August 24-27, 1998
• 30: John R. Smith , Rakesh Mohan , Chung-Sheng Li, Scalable multimedia delivery for pervasive computing, Proceedings of the seventh ACM international conference on Multimedia (Part 1), p.131-140, October 30-November 05, 1999, Orlando, Florida, United States [doi>10.1145/319463.319480]
• 31: Yahoo.com, http://www.yahoo.com
• 32: S. Yau , F. Karim, Context-Sensitive Object Request Broker for Ubiquitous Computing Environments, Proceedings of the 8th IEEE Workshop on Future Trends of Distributed Computing Systems, p.34, October 31-November 02, 2001
• 33: Stephen S. Yau , Fariaz Karim, Context-Sensitive Distributed Software Development for Ubiquitous Computing Environments, Proceedings of the 25th International Computer Software and Applications Conference on Invigorating Software Development, p.263-268, October 08-12, 2001
• 34: Context-Sensitive Middleware for Real-Time Software in Ubiquitous Computing Environments, Proceedings of the Fourth International Symposium on Object-Oriented Real-Time Distributed Computing, p.163, May 02-04, 2001
• 35: C. Yoshikawa, B. Chun, P. Eastham, A. Vahdat, T. Anderson, and D. Culler, "Using smart clients to build scalable services", Proc. Winter 1997 USENIX Technical Conf., Jan. 1997.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.m Miscellaneous

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
content adaptation, mobile computing, performance optimization, pervasive computing, pre-adaptation