Automatic detection of fragments in dynamically generated web pages

ABSTRACT

Dividing web pages into fragments has been shown to provide significant benefits for both content generation and caching. In order for a web site to use fragment-based content generation, however, good methods are needed for dividing web pages into fragments. Manual fragmentation of web pages is expensive, error prone, and unscalable. This paper proposes a novel scheme to automatically detect and flag fragments that are cost-effective cache units in web sites serving dynamic content. We consider the fragments to be interesting if they are shared among multiple documents or they have different lifetime or personalization characteristics. Our approach has three unique features. First, we propose a hierarchical and fragment-aware model of the dynamic web pages and a data structure that is compact and effective for fragment detection. Second, we present an efficient algorithm to detect maximal fragments that are shared among multiple documents. Third, we develop a practical algorithm that effectively detects fragments based on their lifetime and personalization characteristics. We evaluate the proposed scheme through a series of experiments, showing the benefits and costs of the algorithms. We also study the impact of adopting the fragments detected by our system on disk space utilization and network bandwidth consumption.

REFERENCES

• 1: Document Object Model - W3C Recommendation. http://www.w3.org/DOM.
• 2: Edge Side Includes - Standard Specification. http://www.esi.org.
• 3: HTML TIDY. http://www.w3.org/People/Raggett/tidy/.
• 4: H. Bahn, H. Lee, S. H. Noh, S. L. Min, and K. Koh. Replica-Aware Caching for Web Proxies. Computer Communications, 25(3), 2002.
• 5: Ziv Bar-Yossef , Sridhar Rajagopalan, Template detection via data mining and its applications, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511522]
• 6: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 7: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 8: A Fully Automated Object Extraction System for the World Wide Web, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.361, April 16-19, 2001
• 9: K. S. Candan, D. Agrawal, W.-S. Li, O. Po, and W.-P. Hsiung. View Invalidation for Dynamic Content Caching in Multi tiered Architectures. In Proceedings of VLDB-2002, September 2002.
• 10: J. Challenger, A. Iyengar, and P. Dantzig. A Scalable System for Consistently Caching Dynamic Web Data. In Proceedings of IEEE INFOCOM 1999, March 1999.
• 11: J. Challenger, A. Iyengar, K. Witting, C. Ferstat, and P. Reed. Publishing System for Efficiently Creating Dynamic Web Content. In Proceedings of IEEE INFOCOM 2000, May 2000.
• 12: M. C. Chan and T. W. C. Woo. Cache-Based Compaction: A New Technique for Optimizing Web Transfer. In Proceedings of INFOCOM-1999.
• 13: Anindya Datta , Kaushik Dutta , Helen Thomas , Debra VanderMeer , Suresha , Krithi Ramamritham, Proxy-based acceleration of dynamically generated content on the world wide web: an approach and implementation, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564703]
• 14: F. Douglis and A. Iyengar. Application-Specific Delta Encoding Via Resemblance Detection. In Proceedings of the USENIX Annual Technical Conference, June 2003.
• 15: Xiao-Dong Gu , Jinlin Chen , Wei-Ying Ma , Guo-Liang Chen, Visual Based Content Understanding towards Web Adaptation, Proceedings of the Second International Conference on Adaptive Hypermedia and Adaptive Web-Based Systems, p.164-173, May 29-31, 2002
• 16: Terence Kelly , Jeffrey Mogul, Aliasing on the world wide web: prevalence and performance implications, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511484]
• 17: P. Kulkarni, F. Douglis, J. LaVoie, and J. Tracey. Redundancy Elimination Within Large Collections of Files. In Proceedings of the USENIX Annual Technical Conference, June 2004. To appear.
• 18: U. Manber. Finding Similar Files in a Large File System. In Proceedings of USENIX-1994, January 1994.
• 19: J. Mogul. Network Behavior of a Busy Web Server and its Clients. Technical report, DEC Western Research Laboratories, 1995.
• 20: J. Mogul, Y. Chan, and T. Kelly. Design, Implementation, and Evaluation of Duplicate Transfer Detection in HTTP. In Proceedings of NSDI '04, March 2004. To appear.
• 21: P. Mohapatra and H. Chen. A Framework for Managing QoS and Improving Performance of Dynamic Web Content. In Proceedings of GLOBECOM-2001, November 2001.
• 22: M. Naaman, H. Garcia-Molina, and A. Paepcke. Evaluation of ESI and Class-Based Delta Encoding. In Proceedings of WCW - 2003.
• 23: M. O. Rabin. Fingerprinting by Random Polynomials. Technical report, Center for Research in Computing Technology, Harvard University, 1981.
• 24: Sean C. Rhea , Kevin Liang , Eric Brewer, Value-based web caching, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775239]
• 25: Torsten Suel , Patrick Noel , Dimitre Trendafilov, Improved File Synchronization Techniques for Maintaining Large Replicated Collections over Slow Networks, Proceedings of the 20th International Conference on Data Engineering, p.153, March 30-April 02, 2004

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.0 General

General Terms:
Algorithms, Design, Performance

Keywords:
L-P fragments, dynamic content caching, fragment detection, fragment-based caching, shared fragments