A COMPARISON OF PREDICTION ALGORITHMS FOR PREFETCHING IN THE CURRENT WEB
Keywords:
Web prefetching, web performanceAbstract
This paper reviews a representative subset of the prediction algorithms used for Web prefetching classifying them according to the information gathered. Then, the DDG algorithm is described. The main novelty of this algorithm lies in the fact that, unlike previous algorithms, it creates a prediction model according to the structure of the current web. To this end, the algorithm distinguishes between container objects and embedded objects. Its performance is compared against important existing algorithms, and results show that, for the same amount of extra requests to the server, DDG always outperforms those algorithms by reducing the perceived latency up to 70% more without increasing the complexity order.
Downloads
References
B.D. Davison , Assertion: Prefetching with GET is not Good , in Proceedings of the 6th Interna-
tional Workshop on Web Caching and Content Distribution (Boston, USA, 2001)
H.K. Lee and G. Vageesan, K.H. Yum, and E.J. Kim, A PROactive Request Distribution (PRORD)
Using Web Log Mining in a Cluster-Based Web Server, in Proceedings of the International Con-
ference on Parallel Processing (ICPP’06) (Columbus, USA, 2006)
S. Schechter, M. Krishnan, and M.D. Smith, Using Path Profiles to Predict HTTP Requests, in
Proceedings of the 7th International World Wide Web Conference (Brisbane, Australia, 1998)
E. Cohen and H. Kaplan, Prefetching the means for document transfer: a new approach for
reducing Web latency, Computer Networks 39 (4) pp437-455 (2002)
E. Markatos and C. Chronaki, A Top-10 Approach to Prefetching on the Web, in Proceedings of
the INET’ 98 (Geneva, Switzerland, 1998)
Ramesh Sarukkai, Link prediction and path analysis using Markov chains., Computer Networks,
(1-6) pp377-386 (2000), DBLP, http://dblp.uni-trier.de
L. Fan, P. Cao, W. Lin, and Q. Jacobson, Web Prefetching Between Low-Bandwidth Clients and
Proxies: Potential and Performance., in Proceedings of the ACM SIGMETRICS Conference on
Measurement and Modeling Of Computer Systems Atlanta, USA, 1999, DBLP, http://dblp.uni-
trier.de
Z. Su, Q. Yang, Y. Lu, and H-J Zhang, WhatNext: A prediction system for web requests using
N-gram sequence models, in Proceedings of the 1st International Conference on Web Information
Systems and Engineering Conference (Hong Kong, China, 2000)
J. Dom`enech, J. ´e A. Gil, J. Sahuquillo, and A. Pont, Web prefetching performance metrics: A
survey , Performance Evaluation 63 (9–10) pp988–1004 (2006)
J. Zhu, J. Hong, and J.G. Hughes, Using Markov Models for Web Site Link Prediction, in Pro-
ceedings of the 13th ACM Conference on Hypertext and Hypermedia (College Park, USA, 2002)
J. Pitkow and P. Pirolli, Mining Longest Repeating Subsequences to Predict World Wide Web
Surfing, in Proceedings of the 2nd USENIX Symposium on Internet Technologies and Systems
Boulder, USA, 1999
J. Verma, A.K. Sharma. A. Goel A Framework for Prefetching Relevant Web Pages using Predic-
tive Prefetching Engine (PPE), International Journal of Computer Science Issues 7 (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 25th Symposium On Applied Computing (Sierre, Switzerland,
I. Zukerman, D.W. Albrecht, and A.E. Nicholson, Predicting Users’ Requests on the WWW, in
Proceedings of the 7th International Conference on User Modeling (Banff, Canada, 1999)
V.N. Padmanabhan and J.C. Mogul, Using Predictive Prefetching to Improve World Wide Web
Latency, Computer Communication Review 26 (3) pp22–36 (1996)
Z. Jiang and L. Kleinrock, An Adaptive Network Prefetch Scheme, IEEE Journal on Selected
Areas in Communications 16 (3) pp358–368 (1998)
G. Pallis, A. Vakali, and J. Pokorny A clustering-based prefetching scheme on a
Web cache environment, Computers & Electrical Engineering 34 pp309 - 323 (2008),
doi:10.1016/j.compeleceng.2007.04.002
J. Domenech, J.A. Gil, J. Sahuquillo, and A. Pont Using current web page structure to improve
prefetching performance, Computer Networks 54 (9) pp404 – 1417 (2010)
H. Kargupta, A. Joshi, K. Sivakumar, and Y. Yesha (eds), Data Mining: Next Generation Chal-
lenges and Future Directions, Chapter 3 (AAAI Press, 2004)
Q. Yang, J.Z. Huang, and M. Ng, A data cube model for prediction-based web prefetching, Journal
of Intelligent Information Systems 20 (1) pp11–30 (2003)
S. Gunduz and M. T. Zsu, A Web page prediction model based on click-stream tree representation
of user behavior, in KDD ’03: Proceedings of the ninth ACM SIGKDD international conference
on Knowledge discovery and data mining, pp535–540 (Washington, D.C., 2003)
B. Lan, S. Bressan and B.C. Ooi, and K-L Tan, Rule-assisted prefetching in Web-server caching,
in CIKM ’00: Proceedings of the ninth international conference on Information and knowledge
management (McLean, Virginia, 2000)
Y-F Huang and J-M Hsu, Mining Web Logs to Improve Hit Ratios of Prefetching and Caching
, in Proceedings of the 2005 IEEE / WIC / ACM International Conference on Web Intelligence
(Compiegne, France, 2005)
A. Nanopoulos, D. Katsaros, and Y. Manolopoulos, Exploiting Web Log Mining for Web Cach
Enhancement, in Lecture Notes in Artificial Intelligence (LNAI), 2356 pp68–87 (Springer-Verlag,
A. Nanopoulos, D. Katsaros, and Y. Manolopoulos, A Data Mining Algorithm for Gen-
eralized Web Prefetching. IEEE Trans. Knowl. Data Eng. 15 (5) pp1155-1169 (2003),
http://csdl.computer.org/comp/trans/tk/2003/05/k1155abs.htm, DBLP, http://dblp.uni-trier.de
D. Bonino, F. Corno, and G. Squillero , Dynamic Prediction of Web Requests , in Proceedings of
the IEEE Congress on Evolutionary Computation (Canberra, Australia, 2003)
B. Wu and A.D. Kshemkalyani, Objective-Optimal Algorithms for Long-term Web Prefetching,
IEEE Transactions on Computers 55 (1) pp2–17 (2006)
M. Angermann, Analysis of Speculative Prefetching, ACM Mobile Computing and Communica-
tions Review 6 (2) (2002)
J.I. Khan and Q. Tao, Exploiting Webspace Organization for Accelerating Web Prefetching, in
Proceedings of the IEEE/WIC International Conference on Web Intelligence (Halifax, Canada,
D. Duchamp, Prefetching Hyperlinks , in Proceedings of the 2nd USENIX Symposium on Internet
Technologies and Systems (Boulder, USA, 1999)
T.I. Ibrahim and C.Z. Xu, Neural Nets based Predictive Prefetching to Tolerate WWW Latency,
in Proceedings of the 20th IEEE International Conference on Distributed Computing Systems
(Taipei, Taiwan, 2000)
B.D. Davison, Predicting Web Actions from HTML Content, in Proceedings of the 13th ACM
Conference on Hypertext and Hypermedia (College Park, USA, 2002)
A. Sidiropoulos, G. Pallis, D. Katsaros, K. Stamos, A. Vakali, and Y. Manolopoulos Prefetching
in Content Distribution Networks via Web Communities Identification and Outsourcing, World
Wide Web 11 pp39 – 70 (2008), doi: 10.1007/s11280-007-0027-8
T. Palpanas and A. Mendelzon, Web Prefetching Using Partial Match Prediction, in Proceedings
of the 4th International Web Caching Workshop (San Diego, USA, 1999)
J. Domenech, A. Pont, J. Sahuquillo, and J. Antonio Gil, An Experimen-
tal Framework for Testing Web Prefetching Techniques, in Proceedings of
the 30th EUROMICRO Conference 2004 pp214–221 (Rennes, France, 2004),
http://csdl.computer.org/comp/proceedings/euromicro/2004/2199/00/21990214abs.htm
J. Dom`enech, A. Pont, J. Sahuquillo, and J.A. Gil, A User-Focused Evaluation ofWeb Prefetching
Algorithms , Computer Communications 10 (30) pp2213–2224 (2007)
