臺灣博碩士論文加值系統

現今行動計算的研究已經有初步的成果，行動電話與WAP的結合就是正在進行中的一例。然而頻寬礙於無線環境與技術的限制，無法達到與有線網路相同的水準，在行動計算環境上的資訊服務，因此而無法普及。加上使用者的行動，常使得無線訊號無法送達而造成斷訊。
預取技術在頻寬不足的無線網路環境是可行而有用的技術。其主要目的在於將使用者存取網頁時，等待下傳之網路傳輸延遲時間減短。預取利用使用者瀏覽網頁的閒置時間預先取回可能被存取的頁面，而預取的代價是取回較多的資料。傳統的預取方法統計過去使用者的存取紀錄，利用統計的結果或壓縮理論以預測將來的存取。可想而知，這種預測方法對於系統中未存有過去存取記錄的使用者而言，效果將不明顯。
我們提出一個以網頁內容為基礎，加上使用者側寫、伺服器端特殊結構網頁分析、過去使用者集體存取行為等機制的預取方法。 對使用者存取序列作分析，利用資料分類（data classification）的技術分出存取行為接近的使用者群組。使用者側寫經由對使用者瀏覽行為的監測並更新，以表現使用者當時的瀏覽興趣。 伺服器端將行動客戶端歸類至與其存取行為接近的群組，再參考目前使用者瀏覽頁面產生暗示。一般頁面從客戶端所屬的群組中搜尋，特殊結構的網頁則計算其存取傾向，得到此群組將來可能存取頁面，並作為暗示傳給客戶端。行動客戶端收到暗示後計算出最符合目前興趣的頁面，而後預取之。
依據所提之演算法，實作的預取系統，預取命中可以達到30%以上。研究結果發現，使用者存取記錄因為客戶端使用瀏覽器的快取（cache）機制，導致部分存取行為無法被紀錄，因此預取的命中率較低。如果使用者存取記錄越完整，則預取的命中率可再提升。

The research of mobile computing had preliminary results. Take mobile phone integrated with WAP for example, the technique now become practical. However, the bandwidth in the wireless network is still a restriction to information services. Users’ movement cause disconnection, also make the problem more complicated.
Prefetching is a practical and useful technique for hiding the latency of slow wireless link in accessing Web documents. Traditional prefetching techniques rely on past access history to predict future access pattern. These techniques fail to handle new documents effectively.
We propose a semantic-based technique which employs client side user profiles, server side document structure, and collective user access patterns for document prefetching. We identify user groups at server side via document structure analysis and access patterns clustering. A profile represents the corresponding user's current interests. Profiles are updated dynamically by monitoring user browsing behavior. By classifying clients into different user groups based on user profiles, we generate server hints for effective client side prefetching.
According to the prefetch algorithm, we also implemented a prefetch system. The experiment result shown that prefetch ratio can be 30% or higher. We also found that access log can not record users’ access completely because of the mechanism of browsers’ cache. The more information the access log recorded, the higher the prefetch ratio.

第一章 簡介 4
1.1 研究動機 4
1.2研究目的 5
1.3 研究步驟 5
1.4研究成果 7
1.5論文架構 7
第二章 相關研究 8
2.1行動計算環境(Mobile Environment) 8
2.1.1 無線網路介紹 8
2.1.2行動計算介紹 9
2.1.3行動計算環境對資料管理的限制 11
2.1.4解決行動計算產生問題之方法 12
2.2預取（Prefetch）相關研究 14
2.2.1 預取介紹 15
2.2.2預取方式 15
2.2.3其他實作預取之系統 17
2.3 適用行動環境之WWW資訊系統 18
2.3.1支援行動環境之網際網路資訊系統Mobisaic 18
2.3.2動態文件（Dynamic Document） 19
2.3.3 IBM eNetwork WebExpress 20
2.4資料分類（Data Classfication） 21
2.4.1資料分類簡介 22
2.5 Web Server Side Programming簡介 23
2.5.1 CGI（Common Gateway Interface） 23
2.5.2 mod_perl 25
2.5.3Active Server Pages 25
2.5.4 Servlet 25
2.6可程式代理介紹 27
2.6.1 IBM WBI DK for Java 28
第三章 瀏覽行為與網頁結構分析 30
3.1使用者瀏覽行為 30
3.1.1使用者瀏覽已瀏覽網頁的行為 30
3.1.2 Web server存取日誌檔 33
3.1.3 存取模式 34
3.1.4使用者存取網頁的時間區域性與空間區域性 35
3.2網頁結構分析 36
3.2.1 Power Point檔轉換的HTML網頁 36
3.2.2 LaTeX2HTML網頁 38
3.2.3頁框式網頁 38
3.3 與預取策略相關之知識與應用 39
3.3.1 以距離函式衡量使用者存取模式之差異 40
3.3.2 差異度矩陣作為分群依據 41
3.3.3從差異度矩陣區分各使用者群集： 42
3.3.4伺服器端暗示（Server Side Hint） 42
3.3.5客戶端使用者側寫（Client Side User Profile） 43
第四章 預取演算法與系統架構 46
4.1預取演算法 46
4.1.1存取模式樹產生演算法 46
4.1.2內容導向預取演算法 53
4.1.3結構導向預取演算法 56
4.1.3 線上使用者歸類演算法 58
4.2系統架構 59
4.2.1 客戶端預取代理人 60
4.2.2 伺服器端代理人 61
第五章 系統實作與效能評估 63
5.1系統實作 63
5.1.1實驗環境與平台 63
5.1.2系統流程 63
5.2系統效能評估 65
5.2.1預取命中率 66
5.2.2預取、快取與一般方式其傳輸資料量關係 68
5.2.3預取資料量之關係 69
5.2.4預取與否和系統回應時間 70
第六章 結論與未來研究 72
6.1結論 72
6.2問題與討論 72
6.2 未來研究 73

[1] Swarup Acharya, Michael Franklin, Stanley Zdonik. Dissemination-based Data Delivery Using Broadcast Disks, IEEE Personal Communications, Vol 2, No 6, December 1995
[2] Virgilio Almeida, Azer Bestavros, Mark Crovella and Adriana de Oliveira, Characterizing Reference Locality in the WWW, In Proceedings of IEEE PDIS’96: The International Conference in Parallrl and Distributed Information Systems, Miami Beach, Florida, USA, December 1996.
[3] M.F.Arlitt and C.L. Williamson “Web Server Workload Characterization: The search for invariants”. In proc. of the 1996 ACM SIGMETRICS Conference, May 1996.
[4] Ricardo Baeza-Yates; Berthier Ribeiro_Neto, Modern Information Retrieval ,Addison Wesley Longman, Inc. , May 1999, ISBN: 020139829X
[5] M. Berndtsson, B. Lings, Logical Events and ECA Rules. HS-IDA-TR-95-004, Department of Computer Science, University of Skovde, 1995.
[6] M. Campione, K. Walrath, The Java Tutorial, Sun Microsystems Inc., http://java.sun.com/docs/books/tutorial/servlets/, 1999.
[7] S. Chakravarthy, V. Krishnaprasad, Anatomy of a Composite Event Detector, UF-CIS-TR-93-039, University of Florida, FL. 1993
[8] S. Chakravarthy, V. Krishnaprasad, ECA Rule Integration into an OODBMS：Architecture and Implementation, UF-CIS-TR-94-023，University of Florida, FL. 1994
[9] Y.T.Chang, An Active Data Replication Scheme for Mobile Information Management, Department of Computer Science and Information Engineering NDHU, July 1998.
[10] Ken-ichi Chinen, Suguru Yamaguchi. An Interactive Prefetching Proxy Server for Improvements of WWW Latency, INET 97
[11] Carlos R. Cunha and Carlos F. B. Jaccoud, Determining WWW User’s Next Access and Its Application to Pre-fetching, Symposium on Computers and Communication’97, Alexandria, Egypt, 1-3 July 1997
[12] R. Floyd; B. Housel; C. Tait, Mobile Web access using eNetwork Web Express, IEEE Personal Communications , Volume: 5 Issue: 5 , Oct. 1998 Page: 47 —52
[13] William Frakes, Ricardo Baeza-Yates, Information Retrieval: Data Structures and Algorithms, Prentice Hall; ISBN: 0134638379
[14] LINDA GEPPERT &TEKLA S. PERRY Senior Editors, Transmeta's magic show IEEE Spectrum May, 2000 Volume 37 Number 5 http://www.spectrum.ieee.org/pubs/spectrum/0500/tran.html
[15] S.T. Hsu, "A Preferenced-Oriented Approach to Intranet Prefetching" Department of Computer Science and Information Engineering, NDHU, July 1998
[16] Alex Homer, Dave Sussman, Brian Francis; Professional Active Server Pages3.0, Wrox Press Inc., ISBN：1861002610, 1999
[17] Barron C. Housel, George Samaras and David B. Lindquist, WebExpress：A client/intercept based system for optimizing Web browsing in a wireless environment. Mobile Networks and Applications 3, 1998, p.419-431
[18] Jason Hunter, William Crawford, Java servlet programming, O'Reilly & Associates; ISBN: 156592391X, Nov. 1998
[19] Tomasz Imielinski and B. R. Badrinath, Replication & Mobility, WMRD-II,Monterey, CA.
[20] Tomasz Imielinski and B. R. Badrinath, Mobile wireless computing: challenges in data management; Commun. ACM 37, 10 , Oct. 1994, Pages 18 — 28
[21] Quinn Jacobson, Pei Cao, Potential and Limits of Web Prefetching Between Low-Bandwidth Clisnts and Proxies， 3rd International WWW caching workshop 1997
[22] A. K. Jain and R.C. Dubes, Algorithms for Clustering Data. Pentice-Hall advanced reference series, 1988.
[23] Reinhard P. Klemm, ”WebCompanion: A Friendly Client-Side Web Prefetching Agent”, IEEE Tansactions on Knowledge and Data Engineering, Volume: 11 4, July/Aug. 1999, p.577-594
[24] D. Lam; Yingwei Cui; D.C. Cox; J. Widom; A location management technique to support lifelong numbering in personal communications services. Global Telecommunications Conference, 1997. GLOBECOM '97., IEEE , Volume: 2 , 1997 Pages: 704 -710 vol.2
[25] Yi-Bing Lin, Introduction to Mobile Network Management 行動網路管理概論, 維科出版社;ISBN：9578675526, 1997
[26] Chenjie Liu; Pei Cao “Maintaining strong cache consistency in the World-Wide Web” Distributed Computing Systems, 1997., Proceedings of the 17th International Conference on , 1997 , p.12 —21
[27] M. Mouly and M.B. Pautet. The GSM system for Mobile communications. Palaiseau, France, 1992
[28] Rikki N. Nguyen; Azer Bestavros, “Implementation of Server-Assisted Prefetching for the WWW”, Data Engineering Bulletin 19(3): 3-11, 1996.
[29] M.F. Kaashoek; T. Pinckney; J.A. Tauber, Dynamic documents: mobile wireless access to the WWW, Mobile Computing Systems and Applications, 1994. Proceedings., Workshop on , 1995 p.179 —184
[30] S. Sheng, A. Chandrasekaran and R.W. Broderson, A portable multimedia terminal for personal communications. IEEE commun. Mag. Dec. 1992, 64-75
[31] Stuart Schechter; Murali Krishnan and Michael D. Smith, Using user profiles to predict HTTP requests, Seventh World Wide Web Conference in Brisbane, Australia, 1998.
[32] Lindo Tauscher and Saul Greenberg, How People Revisit Web Pages: Empirical Findings and Implications for the Design of History Systems, International Journal of Human Computer Studies, Special issue on World Wide Web Usability, 47(1), p.97-138, Academic Press, 1997.
[33] © 2000 AltaVista Company®, http://www.altavista.com
[34] Apache HTTP server project, http://www.apache.org/httpd.html
[35] Connectix Corp., URL: http://www.connectix.com/products/sed.html
[36] Demonstration of the function of WWW - Markup Conversion, http://www.sinica.edu.tw/www/demo/, 1994
[37] Goto Software, http://www.webearly.com/us/description.htm.
[38] JAVATM SERVLET API The Power Behind the Server, http://java.sun.com/products/servlet/index.html
[39] Netscape Navigator, http://home.netscape.com
[40] Openfind Information Technology INC., http://www.openfind.com.tw
[41] The Apache/Perl Integration Project, http://perl.apache.org.
[42] The Source for Java™ Technology, http://java.sun.com/
[43] WBI Development Kit for Java, http://www.alphaworks.ibm.com/tech/wbidk
[44] http://www.cs.washington.edu/homes/voelker/mobisaic/abs-mobile94.html, Computer Science, University of Washington, Last updated May 1996
[45] 教育部國語推行委員會八十七年口語語料調查報告書，http://www.edu.tw/mandr/result/87oral/index.htm