Abstract

Web prefetching is an effective technique used to mitigate the user perceived latency by making predictions about the user’s future requests and prefetching them before the user actually demands them. In this paper, we present an algorithm that learns from user access patterns and builds a Precedence Graph (PG) that is used to generate the predictions. The difference in the relationship between objects of the same web page and the objects of different web pages are reflected in the graph implementation. It uses simple data structure to implement the graph, which is cost effective and consumes less computational resources. The proposed approach significantly improves the performance of web prefetching by utilizing limited amount of resources as compared to other existing algorithms used for prefetching.

References

• V. Padmanabhan and J. Mogul, “Using Predictive Prefetching to Improve World Wide Web Latency,” Computer Communication Review, vol. 26, no. 3, pp. 22-36, July 1996
• C.R. Cunha and C.F.B. Jaccoud, “Determining WWW User’s Next Access and its Application to Prefetching”, Proceedings of International Symposium on Computers and Communication, pp. 6-11, July 1997
• S. Schechter, M. Krishnan, and M. Smith, “Using Path Profiles to Predict HTTP Requests,” Proceedings of 7th International World Wide Web Conference, also appeared in Computer Networks and ISDN Systems, vol. 20, pp. 457-467, 1998
• E.P. Markatos and C.E. Chronaki, “A Top-10 Approach to Prefetching on the Web”, Proceedings of INET ’98, July 1998
• L. Fan, P. Cao, W. Lin, and Q. Jacobson, “Web Prefetching between Low-Bandwidth Clients and Proxies: Potential and Performance”, Proceedings of SIGMETRICS ’99, pp. 178-187, May 1999
• R.P. Klemn, “Web Companion: A Friendly Client-Side Web Prefetching Agent”, IEEE Transactions on Knowledge and Data Engineering, vol. 11, no. 4, pp. 577-594, 1999
• J. Borges and M. Levene, “Data mining of user navigation patterns”, Lecture Notes in Computer Science, Springer-Verlag, Vol. 1836, pp. 92–111, 1999
• R. Sarukkai, “Link Prediction and Path Analysis Using Markov Chains”, Proceedings of 9th International World Wide Web Conference, 2000
• X. Chen and X. Zhang, “A popularity-based prediction model for web prefetching”, IEEE Computer, march 2003
• A. Nanopoulos, D. Katsaros, and Y. Manolopoulos, "A data mining algorithm for generalized web prefetching”, IEEE Transaction on Knowledge and Data Engineering, vol.15, no.5, pp.1 -16, 2003
• R. Kokku, P. Yalagandula, A. Venkataramani, and M. Dahlin,” NPS: A non-interfering deployable web prefetching system”, Proceedings of the USENIX Symposium on Internet Technologies and Systems, 2003
• C. Bouras, A. Konidaris, and D. Kostoulas, ”Predictive prefetching on the web and its potential impact in the wide area”, World Wide Web: Internet and Web Information Systems, vol.7, pp.143 –179, 2004
• M. Deshpande and G. Karypis, “Selective markov models for predicting web page accesses”, ACM Transactions on Internet Technology, Vol.4, pp.163–184, 2004
• B. D. Davison, “Learning web request patterns”, Web Dynamics: Adapting to Change in Content, Size, Topology and Use, Springer, pp. 435–460, 2004
• J. Domenech, J. Sahuquillo, J. A. Gil, and A. Pont, “The impact of the web prefetching architecture on the limits of reducing user’s perceived latency”, Proceedings of IEEE/WIC/ACM International Conference on Web Intelligence, 2006
• Josep Domenech, Jose A. Gil, Julio Sahuquillo, Ana Pont, “DDG: An Efficient Prefetching Algorithm for Current Web Generation”, In Proceedings of the 1st IEEE Workshop on Hot Topics in Web Systems and Technologies (HotWeb), Boston, USA, 2006
• J. Domenech, J.A. Gil, J. Sahuquillo, A. Pont, “Using current web page structure to improve prefetching performance”, Computer Networks, vol. 54, no. 9, pp. 1404 -1417, 2010
• B. de la Ossa, A. Pont, J. Sahuquillo and J. A. Gil, “Referrer Graph: a low-cost web prediction algorithm”, in Proceedings of the 2010 ACM Symposium on Applied Computing, March 22-26, 2010
• J. Domenech, A. Pont, J. Sahuquillo, and J. A. Gil, “A user focused evaluation of web prefetching algorithms”, Computer Communications, vol.30, no.10, pp. 2213-2224, 2007
• B. de la Ossa, J. A. Gil, J. Sahuquillo and A. Pont, “Improving Web Prefetching by making Predictions at Prefetch”, proceedings of 3rd EuroNGI Conference on Next Generation Internet Networks, pp. 21-27, 2007
• Zhijie Ban, Zhimin GU, Yu Jin, “A PPM Prediction Model Based on Stochastic Gradient Descent for Web Prefetching”, Proceedings of 22nd International Conference on Advanced Information Networking and Applications, pp.166-173, 2008
• B. de la Ossa, J. Sahuquillo, A. Pont, J. A. Gil, "An Empirical Study on Maximum Latency Saving in Web Prefetching," vol. 1, pp.556-559, IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, 2009
• Darin Fisher and Gagin Saksena, “Link prefetching in Mozilla: A server driven approach”, in proceedings of the 8th International Workshop on Web Content Caching and Distribution (WCW 2003), New York, USA, 2003.
• Alexander P. Pons, “Improving the performance of client web object retrieval”, Journal of Systems and Software, vol.74, issue.3, 2005.