跳到主要內容

臺灣博碩士論文加值系統

(3.229.142.104) 您好!臺灣時間:2021/07/27 05:35
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:周彥廷
研究生(外文):YEN-TING CHOU
論文名稱:設計一個新的索引方式以提昇機率天際線的查詢效率
論文名稱(外文):Designing an Index to Enhance the Query Performance for Probabilistic Skyline Searches
指導教授:劉傳銘劉傳銘引用關係
口試委員:俞征武王正豪
口試日期:2011-06-26
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:資訊工程系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:47
中文關鍵詞:索引天際線機率性天際線不確定性資料
外文關鍵詞:IndexSkylineProbabilistic SkylinesUncertain Data
相關次數:
  • 被引用被引用:0
  • 點閱點閱:124
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
天際線計算近年來被廣泛的應用在數據分析上,但隨著資料量增加、須考慮的因素更為多元或是資料類型的轉變等因素,都大大增加運算上的困難,因此越來越多人針對天際線計算去設計出更佳的演算法,以達到更佳的效能。過往在做天際線的運算時,不論是確定性資料或不確定性資料,最常使用的索引技巧大部分為R-Tree,但因為R-Tree常會有重疊的現象發生,往往造成修剪上的效率不佳,因此有人提出Z-Tree的方式,藉此成功地改善了這樣的現象。本論文所提出新的索引方式類似於Z-Tree,主要是針對索引中的節點擺放順序做改變,如此一來可以降低節點彼此間比較的次數,最後的實驗中顯示:在效能上我們的方法將隨著資料量增大或是空間維度升高明顯的提升。

Computing skyline has been widely used in data analysis in recent years, but it has greatly increased the difficulties in the computation with the variety of factors, such as increase in the amount of data, or variation in the type of data… etc., so more and more people try designing a better algorithm to achieve better performance. R-Tree was frequently used when computing skyline on whether certain data or not uncertain data, but it often has overlap between any two nodes result in the inefficiency of pruning, so it was proposed Z-Tree to improve this phenomenon. This paper propose a new way that is similar to Z-Tree, it mainly changes order of placing node in memory to achieve what reducing number of dominant test between any two nodes in high dimensions, the last experiment shows that the performance of the way will be signifi-cantly improved with the increase in the amount of data or dimension.

摘 要 i
ABSTRACT ii
致 謝 iii
目 錄 iv
圖目錄 vi
第一章 前言 1
第二章 相關文獻 4
第三章 相關背景 8
3.1 不確定性資料 8
3.2 天際線(Skyline) 9
3.2.1 確定性資料的天際線 9
3.2.2 不確定性資料下的天際線 11
3.2.3 機率性天際線查詢 13
3.2.4 Top-K機率性天際線查詢 14
3.3 減少征服測試的技巧 14
3.3.1 物件之間的征服測試 14
3.3.2 集合的征服測試 15
3.4 天際線機率上界 16
3.5 Z-Tree 17
第四章 Norn-Tree 19
4.1 Norn-Tree概念 19
4.2 Norn-Tree建立 20
4.2.1 節點的擺放順序 20
4.2.2 建立 21
4.3 Norm-Tree與Z-Tree比較 22
第五章 演算法 25
5.1 資料結構 25
5.2 走訪索引的概念 27
5.3 P-Skyline 28
5.4 作法範例 34
5.5 TopK-Skyline 35
第六章 實驗 37
6.1 實驗環境 37
6.2 P-Skyline資料量對效能的影響 38
6.3 P-Skyline維度對效能的影響 41
6.4 TopK-Skyline資料量和維度變化對效能的影響 43
第七章 結論 45
參考文獻 46


[1] Stephan Borzsonyi, Donald Kossmann and Konrad Stocker, “The Skyline Opera-tor,” ICDE, 2001, 421 - 430.
[2] Charu C. Aggarwal and Philip S. Yu. “A sUSvey of uncertain data algorithms and applications”. IEEE Transaxtions on Knowledge and Data Engineering, 2009, 609 - 623.
[3] Sarvjeet Singh, Chris Mayfield, Rahul Shah, Sunil Prabhakar, Susanne Hambru-sch,Jennifer Neville and Reynold Cheng, “Database Support for Probabilistic At-tributes and Tuples,” In Proceedings of 24th International Conference on Data En-gineering IEEE, 2008.
[4] Jian Pei, Bin Jiang, Xuemin Lin, Yidong Yuan, “Probabilistic Skylines on Uncertain Data,” in VLDB, 2007, 660 - 671.
[5] Mikhail J. Atallah , Yinian Qi , “Computing All Skyline Probabilities for Uncertain Data,” ACM, 2009, 279 - 287.
[6] Dongwon Kim, Hyeonseung Im, and Sungwoo Park, “Computing Exact Skyline Probabilities for Uncertain Databases,” IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2011.
[7] A. Guttman, "R-trees: a dynamic index structure for spatial," in SIGMOD, 1984, 47 - 57.
[8] Jan Chomicki, Parke Godfrey, Jarek Gryz, Dongming Liang, “Skyline with Prescorting,” Data Engineering, 2003. Proceedings. 19th International Conference on, 717 - 719.
[9] Kian-Lee Tan, Pin-Kwang Eng, Beng Chin Ooi, ” Effcient Progressive Skyline Computation,” Proceedings of the 27th VLDB Conference, Roma, Italy, 2001, 301 - 310.
[10] Hyountaek Yong, Jin-ha Kim, and Seung-won Hwang, “Skyline Ranking for Uncertain Data with Maybe Confidence,” Data Engineering Workshop, 2008. ICDEW 2008. IEEE 24th International Conference on, 572 - 579.


[11] Wenjie Zhang, Xuemin Lin, Ying Zhang, Wei Wang, Jeffrey Xu Yu,” Probabilis-tic Skyline Operator over Sliding Windows”, Proceedings of the 2009 IEEE Inter-national Conference on Data Engineering, 1060 - 1071.
[12] Ken C. K. Lee, Baihua Zheng, Huajing Li, Wang-Chien Lee, “Approaching the Skyline in Z Order,” VLDB 2007 Proceedings of the 33rd international conference on Very large data bases, 279 - 290.


電子全文 電子全文(本篇電子全文限研究生所屬學校校內系統及IP範圍內開放)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top