臺灣博碩士論文加值系統

隨著科技的進步，網路上可取得的資料越來越多且複雜，加上各種行動裝置的普及，資料的產生方式越來越多元，如何在大量的資料中找出使用者所需要的資料，一直是一項重要的議題。其中天際線一直是一個熱門的項目。但傳統型天際線逐漸無法應付大量的資料，因而加入分散式的概念，將資料庫切割分成數個小部分，分別以不同的電腦計算，再整合其結果就可以得到原資料庫的天際線。如此可以避開直接計算大量的資料，也省去了升級硬體的成本。近年來研究學者提出了兩個空間切割方法:網格切割以及角度切割，由於空間切割方式的不同，網格切割伺服器間擁有支配關係，可以減少需要計算的伺服器數量;而角度切割後各伺服器可進行平行處理，縮短區域天際線的計算時間。以往兩個方法，擁有各自的優點以及缺點，可以說空間切割方法決定了該方法的特色。
上述的兩個切割方法中，網格切割的伺服器之間的關係是角度切割所不具備的，而角度切割的平行處理也是網格切割所沒有的。因此本篇論文的目的在於融合以往提出網格切割以及角度切割的優點，並將在切割時所必需尋找出來的資料賦予額外的功能，達到更快的執行時間。

As the improvement of computer and internet technologies, more and more data is produced and shared on the internet. How to find the users’ needed information from the large amount of data efficiently is a very important issue. Skyline query is a possible solution of finding useful information from multi-dimentional dataset. However, the time needed to process skyline query increases as the data size increases. Therefore, in this thesis, we proposed a parallel skyline query processing method to find the skyline in a huge amount dataset efficiently. Moreover, to show the benefit of our approach, by comparing to the previous methods, a set of experiment is performed on synthetic and real datasets. The experimenttal results indicated that the proposed approach is outperformed than the previous methods.

第一章 導論 1
第二章 相關研究與背景知識 5
2.1天際線查詢 5
2.2分散式天際線運算 8
2.2.1網格切割天際線運算 10
2.2.2角度切割天際線運算 12
第三章 斜率切割演算法 15
3.1二維度斜率切割演算法 18
3.2高維度斜率切割演算法 25
3.3演算法探討 30
第四章 實驗結果 35
4.1人造資料庫 36
4.1.1反相關性資料 36
4.1.2正相關性資料 39
4.1.3獨立性資料 42
4.2 真實資料庫 44
4.3實驗總結 46
第五章 結論與未來展望 47
參考文獻 49

[1] P. Wu, C. Zhang, Y. Feng, B. Y. Zhao, D. Agrawal, and A. E. Abbadi. “Parallelizing Skyline Queries for Scalable Distribution” In EDBT, pages 112–130, 2006.
[2] A. Vlachou, C. Doulkeridis, and Y. Kotidis, "Angle-based space partitioning for efficient parallel skyline computation," in SIGMOD, 2008, pp. 227 -238.
[3] Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001
[4] J. Chomicki, P. Godfrey, J. Gryz, and D. Liang. Skyline with presorting: Theory and optimizations. In Intelligent Information Systems, pages 595--604, 2005. Also appeared in ICDE'03.
[5] Ken C. K. Lee , Baihua Zheng , Huajing Li , Wang-Chien Lee, Approaching the skyline in Z order, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
[6] Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Shenker, “A scalable content-addressable network “, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, USA
[7] G. Trimponias, I. Bartolini, D. Papadias, and Y. Yang. Skyline Processing on Distributed Vertical Decompositions. IEEE Transactions on Knowledge and Data Engineering, 25(4):850–862, 2013

[8] E. Dellis and B. Seeger. Efficient computation of reverse skyline queries. In Proc. 33rd Int. Conf. on Very Large Data Bases, pages 291–302, 2007.
[9] J. Pei et al. Probabilistic skylines on uncertain data. In VLDB’07, Viena, Austria, September 2007.
[10] Chee-Yong Chan, H.V. Jagadish, Kian-Lee Tan, Anthony K.H. Tung, Zhenjie Zhang. Finding k-Dominant Skylines in High Dimensional Space. SIGMOD’2006.
[11] Yufei Tao , Xiaokui Xiao , Jian Pei, SUBSKY: Efficient Computation of Skylines in Subspaces, Proceedings of the 22nd International Conference on Data Engineering, p.65, April 03-07, 2006
[12] Xuemin Lin , Yidong Yuan , Wei Wang , Hongjun Lu, Stabbing the Sky: Efficient Skyline Computation over Sliding Windows, Proceedings of the 21st International Conference on Data Engineering, p.502-513, April 05-08, 2005
[13]Yufei Tao ,Dimitris Papadias, Maintaining Sliding Window Skylines on Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.18 n.3, p.377-391, March 2006
[14] Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
[15] Boliang Zhang , Shuigeng Zhou , Jihong Guan, Adapting skyline computation to the MapReduce framework:algorithms and experiments, Proceedings of the 16th international conference on Database systems for advanced applications, April 22-25, 2011, Hong Kong, China
[16] M. Hua, J. Pei, W. Zhang, and X. Lin, "Ranking queries on uncertain data: A probabilistic threshold approach," in SIGMOD, 2008.
[17]X. Lian and L. Chen, "Monochromatic and bichromatic reverse skyline search over uncertain databases," in SIGMOD, 2008, pp. 213 -226.
[18] I. F. Ilyas, G. Beskales, and M. A. Soliman, "Survey of top-k query processing techniques in relational database systems," ACM Computing Surveys, 2008.
[19] B. Cui, H. Lu, Q. Xu, L. Chen, Y. Dai, and Y. Zhou, "Parallel distributed processing of constrained skyline queries by filtering," in ICDE, 2008, pp. 546 -555.
[20] João B. Rocha-Junior , Akrivi Vlachou , Christos Doulkeridis , Kjetil Nørvåg, Efficient execution plans for distributed skyline query processing, Proceedings of the 14th International Conference on Extending Database Technology, March 21-24, 2011, Uppsala, Sweden