臺灣博碩士論文加值系統

在資料庫的領域裡，天際線(Skyline)概念與技術受到相當程度的矚目，並被廣泛應用於各領域的實務中。本研究將之導入條件甚為嚴苛的資料串流(Data Stream)環境：滿足隨時間推移資料的或增或刪，還能完全免除對硬碟的存取需求，以達即時獲取、即時反應、即時更新。本研究建構三個演算法，以符合「在資料串流環境下找尋完整的天際線」此一嶄新課題的需求。實驗結果顯示：三演算法都能一如預期滿足上述訴求，差異只在於耗時的多寡。我們在設計演算法時即著眼於不同的增效機制、觀點。最終演算法三勝出，有效降低比對次數是其關鍵。

In Database field, Skyline concepts and techniques have caught many people''s attention and been widely used in various fields. In this study, we would use it in a very harsh condition, Data Stream, and could accomplish some missions like adding or deleting data over time, and completely avoiding accessing hard disks to achieve instant access, instant response and instant update. To meet the demands of this new area, Fully Skyline Computation on Data Streams, we create three algorithms for it. The experimental results showed that: as expected, the three algorithms can meet these demands, and the difference only lay in the amount of time-consuming. The process of designing these algorithms focused on the efficiency of different mechanisms or different views. Finally, Algorithm 3''s performance is better and how to effectively reduce the number of comparisons is the key.

中文摘要 i
英文摘要 ii
致謝 iii
目錄 iv
表目錄 vi
圖目錄 xiv
第一章 緒論 1
第二章 相關研究 3
第三章 研究方法 7
3.1 演算法一 7
3.2 演算法二 20
3.3 演算法三 37
第四章 實驗結果與分析 62
第五章 結論與未來工作 70
參考文獻 72

1.Ronald Fagin, Amnon Lotem, and Moni Naor, “Optimal Aggregation Algorithms for Middleware,” Journal of Computer and System Sciences, Volume 66, Issue 4, Pages: 614-656, June 2003.
2.Antonin Guttman, “R-trees: A Dynamic Index Structure for Spatial Searching,” Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, Pages: 47–57, 1984.
3.Cheqing Jin, Ke Yi, Lei Chen, Jeffrey Xu Yu, and Xuemin Lin, "Sliding-window Top-k Queries on Uncertain Streams," Proceedings of the VLDB Endowment, Volume 1, Issue 1, Pages: 301-312, August 2008.
4.Dimitris Papadias, Yufei Tao, Greg Fu, and Bernhard Seeger, “Progressive Skyline Computation in Database Systems,” Journal of ACM Transactions on Database Systems (TODS), Volume 30, Issue 1, Pages: 41-82, March 2005.
5.Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, and Jun Xu, "Randomized Multi-pass Streaming Skyline Algorithms," Proceedings of the VLDB Endowment, Volume 2, Issue 1, Pages: 85-96, August 2009.
6.Raymond Chi-Wing Wong, Ada Wai-Chee Fu, Jian Pei, Yip Sing Ho, Tai Wong, and Yubao Liu, “Efficient Skyline Querying with Variable User Preferences on Nominal Attributes,” Proceedings of the VLDB Endowment, Volume 1, Issue 1, Pages: 1032-1043, August 2008.
7.Wenjie Zhang, Xuemin Lin, Ying Zhang, Wei Wang, and Jeffrey Xu Yu, "Probabilistic Skyline Operator over Sliding Windows," Proceedings of the 2009 IEEE International Conference on Data Engineering (ICDE), Pages: 1060-1071, 2009.