考慮文件附加價值之快取置換機制

A Cache Document Replacement Mechanism Considering Document Added-value

10.29767/ECS.200406.0006

陳亭志(Toly Chen)；黃汝棋(Ju-Chi Huang)

電子商務網站 ； 快取置換機制 ； 銷售額 ； E-Commerce ； Cache Document Replacment Policy ； Added Value

Electronic Commerce Studies

2卷2期（2004 / 06 / 30）

209 - 227

繁體中文

傳統的快取置換機制以提高快取的效能為主，往往僅考慮文件上次的擷取時間、過去擷取的次數、或是文件大小等因子來置換快取內的文件內容。但是從網站經營的角度來思考，瀏覽者能快速存取的資訊，最好是較能促進其消費行為，俾使網站獲得更大的利益。為達此目的，本研究建構了一個考慮文件附加價值的快取置換機制。此機制考慮四個參數：文件上次擷取時間、文件擷取次數、文件大小、以及文件附加價值以決定文件置換之優先順序。其中文件附加價值的部分，則應用網路探勘的技術，分析使用者的瀏覽路徑以求得各網頁與目標網頁的關聯強度，最後根據一公式決定出提供各文件之快取所能為網站帶來的附加價值。當快取有執行置換之需要時，本置換機制將優先換掉附加價值低、上次擷取時間久、擷取次數少、或太大的文件。如此一來，有消費行為的瀏覽者所常存取的文件，便能留在快取之中，也就是能改善快取對網站消費者的服務品質，從而提升網站之銷售額。為評估此快取置換機制之績效，我們應用PHP-Nuke 建構了一個實驗性的商務網站，並以BCB程式模擬各種使用者的此商務網站之存取，以獲得一些資料作排序分析以Wilcoxon檢定。結果發現新快取置換策略，在customer hit rate與customer byte hit rate的表現上，的確優於其他的置換策略，這顯示了新的快取置換策略的確能為消費者帶來較好的服務效能。

Most traditional cache document replacement policies are focused on the efficiency respect and cache documents are replaced according to their last access times, request frequencies, and sizes. However, the goal of an EC website is to make profits, and the information that can be cached to a user should also promote the user to consume. For this reason, a new cache document replacement policy also considering the value added to the website by caching a document to a user is proposed in this study. As a result, the new policy considers four attributes of every document including the last access time, request frequency, size, and value added to the website. To evaluate the added value to the EC website by caching a document, some data and web mining techniques are applied. Firstly, the aggregation tree of all users’ browsing paths is analyzed to found out the relationship between each web page and the payment page. Then the strength of such a relationship is assessed with the association rule and the absolute-value distance. Based on them, the added value of every cache document can be derived according to an equation modified from the traditional GDSF cache replacement policy. When cache replacement occurs, the document with the smallest added value will be firstly taken away from the cache. In this way, web pages that are more frequently associated with consumption behaviors will be cached to the users with higher probabilities, and users with consumption behaviors (i.e. consumers) can be provided with better caching performance than normal users. An experimental EC website has been constructed in this study to generate some data for evaluating the effectiveness of the proposed mechanism. In the respects of “customer hit rate” and “customer byte hit rate”, the new mechanism outperformed all traditional cache document replacement policies.

1. Arlitt, M.,Cherkasova, L.,Dilley, J.,Fridrich, R.,Jin, T.(1999).Proceedings of the 2nd Workshop on Internet Server Performance.Atlanta GA:
2. Arlitt, M.,Friedrich, R.,Jin, T.(2000).Performance Evaluation of Web Proxy Cache Replacement Policy.Performance Evaluation,39,149-164.
3. Arlitt, M.,Krishnamurthy, D.,Rolia, J.(2001).Characterizing the Scalability of a Large Web-based Shopping System.ACM Transactions on Internet Technology,1(1),44-69.
4. Candan, K. S.,Li, W.-S.,Luo, Q.,Hsiung, W.-P.,Agrawal, D.(2001).Proceedings of the ACM SIGMOD 2001.California, USA:Santa Barbara.
5. Cao, P.,Irani, S.(1997).Proceedings of the USENIX Symposium on Internet Technologies and Systems(USITS).Monterey CA:
6. Chen, M. S.,Park, J. S.,Yu P. S.(1996).Data Mining for Path Traversal Patterns in a Web Environment.Proceedings of the 16th International Conference on Distributed Computing Systems,385-392.
7. Cooley, R.,Mobasher, B.,Srivastava, J.(1997).Web Mining: Information and Pattern Discovery on the World Wide Web.ICTAI`97
8. Law, A. M.,Kelton, W. D.(1991).Simulation Modeling and Analysis.McGraw Hill.
9. Lorenzetti, P.,Rizzo, L.,Vicisano, L.(2000).Replacement Policies for a Proxy Cache.IEEE/ACM Transaction on Networking,8(2),158-170.
10. Ramakrishnan, S.,Yinghui, Y.(2001).Mining Web Logs to Improve Website Organization.The Tenth International Conference on World Wide Web
11. Spiliopoulou, M.,Faulstich, L.(1998).EDBT Workshop WebDB`98.Spain:Valencia.
12. Wang, J.(1999).A Survey of Web Caching Schemes for the Internet.ACM SIGCOMM Computer Communication Review,29,36-46.
13. Williams, S.,Abrams, M.,Standridge, C. R.,Abdulla, G.,Fox, E. A.(1996).Removal Policies in Network Caches for World-Wide Web Documents.Proceedings of Sigcomm`96
14. Wooster, R. P.,Abrams, M.(1997).Proxy Caching that Estimates Page Load Delays.Proceedings of the 6th International WWW Conference