臺灣博碩士論文加值系統

在本論文中，我們提出了一個處理constrained skyline query的演算法。這個演算法名為GCSQP。GCSQP和過去方法不同之處在於它可以將一群constrained skyline queries群組起來，合併處理。
這樣的好處是合併處理後，GCSQP可以省下許多執行dominance test操作的時間，從而加速查詢處理的效率。在本論文中，我們提出了GCSQP的設計理念，說明了演算法的細節，並且以多個實驗證明GCSQP的確可以有效率的加速constrained skyline query的查詢處理。

In this paper, we propose a constrained skyline query processing algorithms. This algorithm is named GCSQP. Compare with preview methods, GCSQP will merge and process them afterward .

The advantage is that after the merger operation, GCSQP can save a lot of time to perform dominance test operation, thereby accelerating query processing efficiently. In this paper, we propose a GCSQP design concept, explain the details of the algorithm, and perform multiple experiments to prove that GCSQP can indeed accelerate query processing efficiently on constrained skyline query.

目錄
致謝
摘要...................................................i
目錄..................................................ii
圖目錄................................................iii
第一章、緒論.............................................1
第二章、文獻探討..........................................6
2.1有使用Inedx的Skyline query演算法....................7
2.1.1 Branch and Bound Search(BBS).................7
2.2無使用Inedx的Skyline query演算法......... ..........9
2.2.1 Nearest neighbor(NN)演算法....................9
2.2.2 Divide and Conquer (D&C)演算法...............10
2.3 Skyline Query Variation.......................11
第三章、研究方法.........................................18
3.1資料結構...........................................1
3.2 GCSQP algorithm ................................21
第四章、實驗成果.........................................25
4.1 Data points個數對效能的影響........................27
4.2 Query個數對效能的影響..............................29
4.3維度對查詢效能的影響.................................30
第五章、結論與建議........................................31


圖目錄
圖1、尋找旅館的天際線查詢例子...............................2
圖2、處理多個 constarined skyline queries的例子...........5
圖3、資料空間............................................8
圖4、R-tree............................................9
圖5、NN演算法...........................................10
圖6、D&C演算法..........................................11
圖7、約束天際線查詢......................................13
圖8、多重約束天際線查詢...................................13
圖9、滑動窗口天際線查詢...................................14
圖10、動態搜尋天際線演算法(第一次結果)......................16
圖11、動態搜尋天際線演算法(第二次結果)......................17
圖12、一個二維資料空間....................................19
圖13、將圖十二建成R-tree.................................19
圖14、GCSQP運作流程I....................................21
圖15、GCSQP運作流程II...................................22
圖16、GCSQP運作流程III..................................23
圖17、GCSQP運作流程IV...................................23
圖18、GCSQP dominance test的虛擬碼......................25
圖19、Correlated dataset下資料點的分佈圖.................26
圖 20、Uniform dataset下資料點的分佈圖....................26
圖 21、資料點個數的實驗結果...............................28
圖 22、查詢個數的實驗結果.................................29
圖 23、維度個數的實驗結果.................................30

[1]Börzsönyi, S., Kossmann, D., Stocker, K.,(2011), "The skyline operator," in Proceedings of ICDE, pp. 421-430.
[2]Chan, C. Y., Jagadish, H.V., Tan, K.-L., Tung, A.K.H., Zhang, Z.,( 2006), "Finding k-dominant skylines in high dimensional space," in Proceedungs of SIGMOD, pp. 503-514.
[3]Dellis, E., Vlachou, A., Vladimirskiy, I., Seeger, B., Theodoridis, Y., (2006), "Constrained subspace skyline computation," in Proceedings of CIKM, pp. 415-424.
[4]Tao, Y., Xiao, X., Pei, J., (2007), "Efficient skyline and top-k retrieval in subspaces," IEEE TKDE 19(8), pp. 1072-1088.
[5]Papadias, D., Tao, Y., Fu, G., Seeger, B. ,(2005), "Progressive skyline computation in database systems," ACM TODS 30(1), pp. 41-82.
[6]Ken C. K. Lee, Wang-Chien Lee, Baihua Zheng, Huajing Li, and Yuan Tian , (2010),"Z-SKY: an efficient skyline query processing framework based on Z-order," VLDB 19, pp.333-362.
[7]Lijiang Chen, Bin Cui, and Hua Lu,(2011),"Constrained skyline query processing against distributed data sites," IEEE TKDE 23(2), pp.204-271.
[8]Yi Zhuang, Qing Li, and Lei Chen, (2008), "Multi-query Optimization for Distributed Similarity Query Processing," in Proceedings of ICDCS, pp. 639-646.
[9]Bartolini, I., Ciaccia, P., Patella, M., (2006), "SaLSa: Computing the skyline without scanning the whole sky," In Proceedings of EDBT, pp. 405-414.
[10]Roy P., Seshadri S., Sudarshan S., and Bhobe S.,(2000), "Efficient and Extensible Algorithms for Multi Query Optimization", in Proceedings of ACM SIGMOD.
[11]Xiaopeng Xiong, Mohamed F. Mokbel and Walid G. Aref,(2005)," SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases," in Proceedings of ICDE, pp. 643-654.
[12]Xiaopeng Xiong, Mohamed F. Mokbel and Walid G. Aref, (2004), " SINA: Scalable Incremental Processing of Continuous Queries in Spatiotemporal Databases," in Proceedings of ACM SIGMOD, pp. 623 - 634.
[13]Bernhard Braunmüller, Martin Ester, Hans-Peter Kriegel, and Jörg Sander, (2001)," Multiple Similarity Queries: A Basic DBMS Operation for Mining in Metric Databases," IEEE TKDE 13(1), pp.79-95.
[14]DimitrisPapadias , YufeiTao,Greg Fu, Bernhard Seeger,(2003)," An Optimal and Progressive Algorithm for Skyline Queries"ACM SIGMOD', San Diego, California, USA.
[15] I-Fang Su, Yu-Chi Chung, Yuan-Ko Huang, and Chang-Ming Tsai, (2013),"An Efficient Query Processing Algorithm for MultipleConstrained Skyline Queries"International Journal of e-Education, e-Business,e-Management and e-Learning, Vol. 3, No. 6.
[16] Jin-xianLin,Jing-jing Wei,(2008),"Constrained Skyline Computing over Data Streams" IEEE International Conference on e-Business Engineering.
[17] Kossmann, D., Ramsak, F., & Rost, S. (2002, August). Shooting stars in the sky: An online algorithm for skyline queries. In Proceedings of the 28th international conference on Very Large Data Bases (pp. 275-286). VLDB Endowment.
[18] Roussopoulos, N., Kelley, S., & Vincent, F. (1995, June). Nearest neighbor queries. In ACM sigmod record (Vol. 24, No. 2, pp. 71-79). ACM.
[19] Vlachou, A., Doulkeridis, C., Kotidis, Y., & Vazirgiannis, M. (2007, April). SKYPEER: Efficient subspace skyline computation over distributed data. InData Engineering, 2007. ICDE 2007. IEEE 23rd International Conference on(pp. 416-425). IEEE.
[20] Lee, J., You, G. W., & Hwang, S. W. (2009). Personalized top-k skyline queries in high-dimensional space. Information Systems, 34(1), 45-61.
[21] Chan, C. Y., Jagadish, H. V., Tan, K. L., Tung, A. K., & Zhang, Z. (2006, June). Finding k-dominant skylines in high dimensional space. In Proceedings of the 2006 ACM SIGMOD international conference on Management of data (pp. 503-514). ACM.