跳到主要內容

臺灣博碩士論文加值系統

(54.224.133.198) 您好!臺灣時間:2022/01/29 20:46
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:高明慶
研究生(外文):Ming-Ching Kao
論文名稱:延伸式標籤語言資料庫上的預測性快取記憶體管理機制
論文名稱(外文):A Predictive Cache Management Policy for XML Databases
指導教授:曾新穆曾新穆引用關係
指導教授(外文):Shin-Mu Tsengsm
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:67
中文關鍵詞:快取記憶體管理機制延伸式標籤語言資料庫資料探勘循序樣式預測技術
外文關鍵詞:cache management policyXML databasedata miningsequential patternsprediction techniques
相關次數:
  • 被引用被引用:1
  • 點閱點閱:426
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:2
快取記憶體管理機制最主要的優點就是能夠縮短使用者查詢的執行時間,目前已有一些相關的研究被發表出來。然而儘管延伸式標籤語言資料庫變的越來越普遍,可是將快取記憶體管理機制運用到延伸式標籤語言資料庫的研究仍是相當有限,所以本研究提出了運用在延伸式標籤語言資料庫上的一個新的快取記憶體管理機制,我們稱之為SPIP( Sequential- Pattern and Interest-Interval Prediction ) 。
這個SPIP機制可分成兩個主要部分:1.探勘機制:從使用者的查詢記錄檔中透過資料探勘的技術去發掘使用者有興趣的規則。2.預測快取機制:將使用者最常查詢的問題答案和我們所發現的有趣規則其所代表的答案預先載入到快取記憶體中。透過實驗的評估我們可以發現SPIP不論是在命中率或是不同系統狀況下的執行時間均比其他的快取機制如LRU都優良。
The main advantages of cache management policies are the response time to an user’s query can be shorten and a number of relevant studies have been proposed. However, the researches on integrating cache management policies into XML database systems are still very limited despite that XML databases have become more and more popular. This research presents a new cache memory replacement policy named SPIP (Sequential-Pattern and Interest-interval Prediction) for XML databases.
The SPIP policy consists of two main components: 1) The mining method that uses a data mining technique to discover the user’s interesting rules from the user query log, 2) The predictive caching policy which preload into cache memory the results of the query the user is most likely to ask based on the current user query and the discovered interesting rules. Through experimental evaluation, SPIE was shown to perform better than other caching policies like LRU in terms of the cache hit ratio and the query response time under various system conditions.
英文摘要………………………………………………………………I
中文摘要………………………………………………………...II
誌謝…………………………………………………………..III
目錄………………………………………………………..IV
表目錄…………………………………………………………………VII
圖目錄………………………………………………………...VIII

第一章 導論…………………………………………………1
1.1 研究背景……………………………………………………………………1
1.2 研究動機……………………………………………………………………1
1.3 解決方法……………………………………………………………………2
1.4 本論文內容與架構…………………………………………………………4
第二章 相關研究………………………………………………………………...5
2.1 XML…………………………………………………………………………5
2.1.1 XML的特性…..….…………………………………………………6
2.1.2 XML Database…..….……………………………………………….8
2.1.2.1 Lore……….………………………………..………………….8
2.1.2.2 OEM……….…………………………..……………………...9
2.2 Generalized Sequential Patterns…………………………………………....10
2.3 使用者查詢喜好分析……………………………………………………..12
2.4 快取記憶體置換機制……………………………………………………..15
2.4.1 LRU……..….………………………………………………………...16
2.4.2 LFU………..….……………………………………………………...16
第三章 預測性快取記憶體管理機制………………………………………17
3.1 預測性快取記憶體管理機制之特性……………………………………..17
3.2 預測性快取記憶體管理機制之架構…..…………………………………18
3.3 探勘機制…………………………………………………………………..20
3.3.1 查詢記錄檔處理………………………………………………….....21
3.3.2 探勘機制步驟.………………………………………………….…...23
3.4 回答機制…………………………………………………………………..29
3.4 快取機制…………………………………………………………………..31
第四章 效能分析……………………………………………………………….35
4.1 實驗環境之建置…………………………………………………………..35
4.1.1 測試環境…………………………………………………...………..35
4.1.2 測試資料…………………………………………………...………..35
4.2 實驗設計…………………………………………………………………..37
4.2.1 基本模組…..….……………………………………………………..38
4.2.2 實驗一:改變快取記憶體的容量大小…………………………….43
4.2.3 實驗二:改變找出前N名問題的N值……………………………45
4.2.4 實驗三:改變最小支持度標準…………………………………….47
4.2.5 實驗四:改變在算可接受的緩衝時間時的R1…………………….50
4.2.6 實驗五:改變排名函數中的參數α1及α2………………………51
4.2.7 實驗六:改變測試資料的筆數…………………………………….52
4.2.8 實驗七:改變問題種類數目……………………………………….54
4.2.9 實驗八:改變生成查詢記錄檔案內兩個問題之間的時間間隔….56
4.3 實驗結果歸納………………………………………….…..59
第五章 結論與未來研究方向
5.1 結論………………………………………………………………..61
5.2 未來研究方向…………………………………………………..61
參考文獻……………………………………………………………..62
[1] S. Abiteboul. Querying semistructured data. In Proceedings of the International Conference on Database Theory, January 1997.
[2] S. Abiteboul, R.Goldman, J.McHugh, V. Vassalos, and Y.Zhuge. Views for semistructured data. In Proceedings of the Workshop on Management of Semistructured Data. May,1997.
[3] Alan Jay Smith, “Cache Memories”. ACM Computing Surveys (CSUR) Volume 14 , Issue3(September 1982) , pp. 473 - 530 . IEEE/ACM Transactions on Networking, Vol. 8, No. 2, 2000, pp.158-170.
[4] S. Abiteboul, D. Quass, J. McHung, J.Widom and J. Wiener. The Lorel Query Language for Semistructured Data. Joutnal of Digital Libraries. November 1996.
[5] R. Agrawal, R. Srikant. “Fast Algorithm for Mining Association Rules.” Proc. Of the 20th Very Large Data Bases (VLDB-94), pp.487-499, Santiago, Chile, 1994.
[6] R. Agrawal and R. Srikant, “Mining Sequential Patterns.” In Proc. of the 11th Int’l Conference on Data Engineering, Taipei, Taiwan, March 1995
[7] F. Bancilhon, C.Delobel, and P.Kanellakis, editors. Building an Object-Oriented Database Sysyem : The Story of O2. 1992
[8] D. W. Cheung, J. Han, V. T. Ng, and C. Y. Wong. “Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique.” In Proc. of the International Conference on Data Engineering, pages 106-114, 1996.
[9] P. Cao and S. Irani, “GreedyDual-size: A cost-aware WWW proxy caching algorithm.” Proc. of USENIX Symposium on Internet Technology and Systems, 1997, pp.165-173.
[10] X. Du, Z. Liu and N. Ishii “Discovering of User-Interests from Range Queries.” Proc. of the 9th Int’l Conference on Database and Expert Systems Applications (DEXA), Vienna, Austria, August, 1998.
[11] K.-S. Fu, Y. T. Chen, and G. P. Cardillo, “A dynamic programming approach to sequential pattern recoginition” IEEE Trans. Part. Anal. Mach. Intell., vol. PAMI-8, no. 3, pp. 313-326, 1986.
[12] R.G.G. Cattell. The Object Database Standard: ODMG-93. Morgan Kaufmuann,1994
[13] M. N. Garofalakis, R. Rastogi, and k. Shim, “SPIRIT: Sequential Pattern Mining with Regular Expression Constraints”, Proc. of 25th International Conference on Very Large Databases, pp. 223~234, September, 1999.
[14] R. Goldman and J. Widom. DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. Proceedings of the Twenty-Third International Conference on Very Large Data Bases, pages 436-445, Athens,Greece,
August 1997.
[15] Jiawei Han, Jian Pei, Behzad Mortazavi-Asl, et. al, “FreeSpan: frequent pattern-projected sequential pattern mining.” Proc. of the 6th ACM SIGKDD nt’l Conference on Knowlwdge discovery and data mining (KDD), Boston, Massachusetts, United States,2000.
[16] Han, J., Pei, J., Mortazavi-Asl, B., Chen, Q., Dayal, U. and Hsu, M.-C. “Frequent pattern projected sequential pattern mining”, In proc. 2000 Int. Conf. Knowledge Discovery and Data mining (KDD) 355-359, Boston, MA, August 2000.
[17] M.Kifer, W.Kim, and Y.Sagiv. Querying object-oriented databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data, June 1992.
[18] D. Lee, et al., ”On the Existence of a Spectrum of Policies the Subsumes LRU,LFU Policies.” Proc. of ACM SIGMETERICS Conference,1999.
[19] Yi Li, Kevin Lü, “Performance Issues of a Web Databae”. In Proceedings of the 11th International Conference on Database and Expert Systems Applications, London, UK, September 4-8, 2000, pp. 825-834.
[20] Jason McHugh, Serge Abiteboul, Roy Goldman, Dallan Quass, Jennifer Widom. Lore: A Database Management System for semistructured Data. SIGMOD Record, 26(3): 54-66, September 1997.
[21] J. Melton and A.R. Simon. Understanding the New SQL: A Complete Guide. 1993
[22] Y. Papakonstantinou, II. Garcia-Molina, and J. Widom, “Object exchange across heterogeneous information sources.” Prof. of the 11th Int’l Conference on Data Engineering, pp.251-260, Taipei, Taiwan, March 1995.
[23] John T. Robinson, Murthy V. Devarakonda, “Data cache management using frequency-based replacement”, In Proceedings of the ACM conference on Measurement and modeling of computer systems, Univ. of Colorado, Boulder,
Colorado, United States, 1990, pp134 – 142.
[24] L. Rizzo and L. Vicisano, “Replacement Policies for a Proxy Cache.”
[25] R. Srikant and R.Agrawal. “Mining Sequential Patterns: Generalizations and Performance Improvements”. Research Report RJ9994, IBM Almade Research Center, San Jose, California, December 1995.
[26] R. Srikant and R. Agrawal, “Mining Sequential Patterns: Generalizations And Performance Improvements.” Proc. of the 5th Int'l Conference on Extending
Database Technology (EDBT), Avignon, France, March 1996.
[27] Dongwook Shin, Hyuncheol Jang and Honglan Jin. BUS: an effective indexing and retrieval scheme in structured documents. Proceedings of the third ACM Conference on Digital libraries. June 23 - 26, 1998
[28] Anthony K. H. Tung, Y. C. Tay and Hongjun Lu, “BROOM: Buffer Replacement using Online Optimization by Mining”, In Proceedings of the 7th International Conference on Information and Knowledge Management,
Bethesda, Maryland, USA, November 3-7, 1998, pp.185-192.
[29] Li-Cheng Wu, Jorng-Tzong Horng, Baw-Jhiune Liu, Chin-Yea Wang, Gwo-Dong Chen. Indexing Semistructured Data Using PATRICIA Tree. DEXA 2000: 859-868
[30] Mohammed J. Zaki, ” Efficient Enumeration of Frequent Sequences.” Proc. Of the 7th Int’l Conference on Information and Knowledge Management (CIKM),Bethesda, Maryland, USA, November, 1998.
[31] Mohammed J. Zaki, “Sequence mining in categorical domains: incorporating constraints.” Proc. of the 9th Int’l Conference on Information and Knowledge Management (CIKM), McLean, Virginia, United States, 2000
[32] W3C, “Extensible Markup Language ( XML ) 1.0 Recommendation”, http://www.w3c.org/TR/1998/REC-XML-19980210.html, February 1998.
[33] W3C, “HTML 4.01 Specification”, http://www.w3c.org/TR/html401, December 1999.
[34] 許毅嘉, “關聯法則應用於代理伺服器上之快取置換機制”, 碩士論文, 國立中興大學資訊科學研究所, 中華民國, 2001.
[35] 陳桂惠, “WWW代理伺服器的部份快取置換策略”, 碩士論文, 元智大學資訊工程研究所, 中華民國, 2000.
[36] 林昇慶, “XML文件資料庫系統”, 碩士論文, 國立台灣大學資訊工程研究所, 中華民國, 2001.
[37] 方乃騏, “Generalizing Sequential Pattern Discovery: Signed and Quantitative Sequential Patterns”, 碩士論文, 中山大學, 中華民國,1999.
[38] 方世榮, “統計學導論二版”,華泰書局,1995.
[39] 何淑媛, “XML與軟體代理人於電子資料交換之應用研究”, 碩士論文, 逢甲大學資訊工程研究所, 中華民國, 2002.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top