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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:邱文宗
研究生(外文):Wen-Tzung Chiou
論文名稱:利用鍵值和存取頻率改善調整時間之樹狀廣播結構
論文名稱(外文):A Tree Broadcast Structure Using Key and Frequency to Improve Tuning Time
指導教授:賈坤芳
指導教授(外文):Kuen-Fang Jea
學位類別:碩士
校院名稱:國立中興大學
系所名稱:資訊科學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:64
中文關鍵詞:廣播機制調整時間樹狀搜尋結構
外文關鍵詞:broadcast mechanismtuning timetree search structure
相關次數:
  • 被引用被引用:1
  • 點閱點閱:956
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
摘要
在無線通訊環境中,資訊的取得不受任何限制。但因為無線裝置(手機或PDA等) 電池能源有限,讓行動客戶端在使用無線裝置時,受到限制。所以如何讓行動客戶端有效率的下載資訊,延長電池能源使用的時間,已成為目前需要解決的問題。現今相關研究大多在廣播頻道中,加入額外資訊,縮短行動客戶端下載資料的時間。例如雜湊機制將雜湊函數放到廣播頻道中,而索引機制則將索引資訊放入廣播頻道。
本研究利用資料使用頻率的差異性,建構樹狀搜尋結構作為索引,並以階層對應到各個廣播頻道的方式,將資料放到各個廣播頻道。利用樹狀搜尋結構找尋資料,可加速高頻資料的搜尋,達到節省能源的目的。本研究中,觀察樹狀搜尋結構,得到了幾個在搜尋上的特性。第一為搜尋所下載的資料,其鍵值順序和頻率順序一致。第二為節點間的搜尋為磁帶搜尋模式。第三為整體搜尋成本有一上限值。在實驗中,以隨機分佈、Zipf分佈及80-20 Rule分佈做為資料存取頻率,針對影響樹狀搜尋結構的參數做調整,觀察調整時間的增減情況。其中改變最大fanout時,對樹的高度、調整時間及存取時間不會有影響。改變資料個數時,調整時間和存取時間都隨著資料個數的增加而增加。本研究跟[JC00]的機制比較,存取時間會變差10%左右,在調整時間方面則改善40%~70%。
第一章 簡介………………………………………………………………..…………1
第二章 相關研究………………………………………………………………..……4
2.1單一廣播頻道之廣播機制…………………………………………………..4
2.1.1(1,m)索引機制………………………………………………………...4
2.1.2雜湊機制……………………………………………………………...5
2.2多重廣播頻道之廣播機制…………………………………………………..6
2.2.1以Alphabetic Huffman Tree為基礎的廣播結構……………..……...6
2.2.2利用pruning方式找到最佳的廣播結構……………………………..6
2.2.3依資料頻率分群所建構的廣播結構……………………………...…7
2.2.4減少資料平均等待時間所建構的廣播結構……………………...…8
2.3總結…………………………………………………………………………..9
第三章 問題及方法描述……………………………………………………………11
3.1問題定義……………………………………………………………………11
3.2方法描述……………………………………………………………………14
3.2.1選取備取資料……………………………………………………….14
3.2.2利用頻率順序成本和鍵值順序成本解決不一致現象…………….15
3.2.3利用資料鍵值將資料分群………………………………………….17
3.3範例…………………………………………………………………………17
3.4建構樹狀搜尋結構演算法…………………………………………………19
第四章 廣播機制……………………………………………………………………22
4.1資料桶結構…………………………………………………………………22
4.2建立廣播頻道………………………………………………………………23
4.2.1樹狀搜尋結構與廣播頻道的對應方式…………………………….23
4.2.2計算廣播頻道資料桶內指標指示的時間………………………….25
4.3行動客戶端搜尋鍵值………………………………………………………29
第五章 樹狀索引結構分析…………………………………………………………32
5.1名詞定義……………………………………………………………………32
5.2樹狀搜尋結構特性…………………………………………………………34
5.2.1階層路徑間鍵值存取頻率的關係………………………………….34
5.2.2磁帶搜尋模式(Tape Searching Model)…….…..……………...…….35
5.2.3整體搜尋成本之上限值…………………………………………….37
5.3整調時間及存取時間之分析………………………………………………40
5.3.1調整時間…………………………………………………………….40
5.3.2存取時間…………………………………………………………….40
5.3.3相關研究的比較…………………………………………………….41
第六章 實驗及結果分析……………………………………………………………43
6.1實驗環境及資料來源………………………………………………………43
6.2實驗目的及參數設定……………………………………………………44
6.3實驗結果與分析……………………………………………………………47
第七章 結論及未來方向……………………………………………...…………….62
參考文獻………………………………………………………………...…………...63
[CK99] Y. D. Chung and M. H. Kim, “QEM : A Scheduling Method for Wireless Broadcast Data,” Proceedings of the 6th International Conference on Database Systems for Advanced Application, 1999, pp.135-142.
[CLR90] T. H Cormen, C. E Leiserson, R. L Rivest, Introduction to Algorithms, The MIT press, 1990.
[HLL98] Q. Hu,D. L. Lee and W. -C. Lee, “A Comparison of Indexing Methods for Data Broadcast on the Air,” Proceedings of the 12th International Conference on Information Networking, 1998, pp.656-659.
[IB94] T. Imielinksi and B. Badrinath, “Mobile Wireless Computing : Challenges in Data Management,” Communication of the ACM, Vol.37, No.10, 1994, pp.18-28.
[IVB94a] T. Imielinski, S. Viswanathan and B. R. Badrinath, “Energy Efficient Indexing on Air,” Proceedings of 1994 ACM-SIGMOD International Conference on Management of Data, 1994, pp. 25-36.
[IVB94b] T. Imielinski, S. Viswanathan and B. Badrinath, Data on Air :Organization and Access, Technical Report, Department of Computer Science, Rutgers University, U.S.A.,1994.
[IVB94c] T. Imielinski, S. Viswanathan and B. R. Badrinath, “Power Efficient Filtering of Data on Air,” Proceedings of 4th International Conference on Information and Knowledge Management of Data, 1994, pp. 245-258.
[JC00] K. F. Jea and S. Y. Chen, “An Energy Saving Broadcast Mechanism to Support Skewed Data Access in The Wireless Environment,” Proceedings of 2000 Workshop on Internet & Distributed Systems, Vol.2, 2000, pp. 153-162.
[Kn73] D. E Knuth, The Art of Computer Programming, Vol.3 (Addison-Wesley), 1973.
[LC00] S. C. Lo and A. L. P. Chen, “Optimal Index and Data Allocation in Multiple Broadcast Channels” Proceedings of the 16th International Conference on Data Engineering, 2000, pp.293-302.
[LL96a] W.-C. Lee and D. L. Lee, ”Using Signature Techniques for Information Filtering in Wireless and Mobile Environments,” Distributed and Parallel Database, Vol.4, No. 3, 1996, pp.205-227.
[LL96b] D. L. Lee and W. -C. Lee, ”On Signature Caching of Wireless Broadcast and Filtering Services,” Proceedings of the 2nd International Mobile Computing Workshop, 1996, pp15-24.
[PC00] W. C. Peng and M. S Chen, “Dynamic Generation of Data Broadcasting Programs for a Broadcast Disk Array in a Mobile Computing Environment,” Proceedings of the ACM 9th Internal Conf. on Information and Knowledge Management, November 6-10, 2000, pp. 38-45.
[SV96] N. Shivakumar and S. Venkatasubramanian, “Efficient Indexing for Broadcast Based Wireless Systems,” Mobile Network and Applications, Vol.1, 1996, pp. 433-446.
[TYE99] K. L. Tan, J. X. Yu, and P. K. Eng, “Supporting Range Queries in a Wireless Environment with Nonuniform Broadcast,” Data & Knowledge Engineering, Vol. 29, 1999, pp. 201-221.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔