臺灣博碩士論文加值系統

在偏好查詢中，天際線查詢常為使用者所採用。在實際的環境下，資料並非一成不變，通常會隨著時間變動，部分資料會隨著時間更新，而須天際線維護。刪除更新前的資料再插入更新後的資料或是插入更新後的資料再刪除更新前的資料是更新部分資料後天際線維護最簡單的想法。但是刪除更新前的資料後原資料的支配關係會隨之消失，可能會增加許多暫時的天際線點；隨後插入更新後的資料，這些暫時的天際線點又再度被支配，增加支配測試次數。整體來說，不論哪種方法都須對整個資料庫執行兩次支配測試，而效能因此降低。
本篇論文的目的是依據更新前的資料以及更新後的資料的支配關係，加上支配關係的遞移性，簡化支配測試次數，以達到更快維護部分資料更新後的天際線集合。

Skyline query is often adopted by user in the preference query. Generally, the data changes with time. Because partial data was updated with time, we need to maintain the correct skyline. Two simple ways to cope with the data updated situation are deleting the updated data first and then inserting the object as a new one or inserting the updated object first and then deleting the old one. However data deletion breaks the dominance relationship, and generates a lot of temporary skyline points. Moreover, if data updated is treated as data deletion/insertion, we need to perform dominance test to all database twice which is inefficient to maintain skyline in the data partial updated situation.

In this thesis, by considering the dominance relationship between the data before updated and after updated, an efficient method for maintaining skyline is proposed. In addition, the transitivity of dominance property is applied. Moreover, a set of simulation is performed to show the benefit of the approach.

目錄
第一章 導論................................1
第二章 相關研究.............................3
第三章 背景知識.............................5
3.1 天際線查詢與其特性.........................5
3.2 Z-排序與支配關係..........................6
3.3 Z-區間與支配關係..........................8
3.4 Z-SKY演算法.............................11
3.5 Z-插入與Z-刪除...........................13
第四章 主要演算法 ...........................................15
4.1更新前的資料與更新後的資料的支配關係...........15
4.2 主要演算法...............................19
第五章 實驗結果.............................29
5.1實驗數據..................................29
5.2實驗總結..................................36
第六章 結論與未來工作........................37
參考文獻.....................................39

圖目錄
圖一、資料支配/被支配區域示意圖...................5
圖二、Z-位址示意圖.............................6
圖三、Z-位址與支配/被支配區域示意圖...............7
圖四、Z-位址連續區間示意圖.......................8
圖五、Z-區間與RZ-區間示意圖......................9
圖六、RZ-區間之間的支配關係示意圖..................9
圖七、資料點p與RZ-區間的支配關係示意圖.............10
圖八、Z-SKY演算法示意圖.........................12
圖九、Z-SKY演算法執行示意圖......................13
圖十、存放天際線集合的B+樹示意圖...................13
圖十一、更新資料流程圖............................22
圖十二、將p_3更新成p_3^'示意圖....................23
圖十三、結束p_3^'更新後示意圖......................24
圖十四、將p_5更新成p_5^'示意圖.....................25
圖十五、將p_6更新成p_6^'示意圖.....................26
圖十六、將p_7更新成p_7^'示意圖.....................26
圖十七、正相關資料處理不同資料筆數的執行時間...........30
圖十八、負相關資料處理不同資料筆數的執行時間...........30
圖十九、獨立資料處理不同資料筆數的執行時間.............31
圖二十、正相關資料處理不同更新比例的執行時間...........32
圖二十一、負相關資料處理不同更新比例的執行時間..........32
圖二十二、獨立資料處理不同更新比例的執行時間............33
圖二十三、正相關資料處理不同維度資料的執行時間..........33
圖二十四、負相關資料處理不同維度資料的執行時間..........34
圖二十五、獨立資料處理不同維度資料的執行時間............34
圖二十六、MLB資料處理不同維度資料的執行時間............35
 
表目錄
表一、機票屬性......................................1
表二、更新後機票屬性.................................2
表三、實驗參數.....................................29
 

[1] W. T. Balke, U. Guntzer, and J. X. Zheng, “Efficient Distributed Skylining for Web Information Systems,” Proc. of EDBT, pp. 256–273, 2004.

[2] I. Bartolini, P. Ciaccia, and M. Patella, “SaLSa: Computing the Skyline without Scanning the Whole Sky,” Proc. of CIKM, pp. 405–414, 2006.

[3] S. Börzsönyi, D. Kossmann, and K. Stocker, “The Skyline Operator,” Proc. of ICDE. 421–430, 2001

[4] C. Y. Chan, H. V. Jagadish, K.-L. Tan, A. K. H. Tung, and Z. Zhang, “Finding K-Dominant Skylines in High Dimensional Space,” Proc. of SIGMOD, pp. 503–514, 2006.

[5] J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, “Skyline with Presorting,” Proc. of ICDE, pp. 717–816, 2003.

[6] E. Dellis, A. Vlachou, I. Vladimirskiy, B. Seeger, and Y. Theodoridis, “Constrained subspace skyline computation,” Proc. of CIKM, pp. 415–424, (2006)

[7] P. Godfrey, R. Shipley, and J. Gryz, ”Maximal Vector Computation in Large Data Sets,” Proc. of VLDB conference, pp. 229–240, 2005.

[8] Z. Huang, C. S. Jensen, H. Lu, and B. C. Ooi, “Skyline Queries Against Mobile Lightweight Devices in MANETs,” Proc. of ICDE, p. 66, 2006.
[9] D. Kossmann, F. Ramsak, and S. Rost, “Shooting Stars in the Sky: An Online Algorithm for Skyline Queries,” Proc. of VLDB conference, pp. 275–286, 2002.

[10] K. C. K. Lee, W. C. Lee, B. Zheng, H. Li, and Y. Tian, “Z-SKY: An efficient Skyline Query Processing Framework Based on Z-order,” The VLDB Journal 19(3), 333–362 ,2010

[11] X. Lin, Y. Yuan, W. Wang, and H. Lu, “Stabbing the Sky: Efficient Skyline Computation over Sliding Windows,” Proc. of ICDE, pp. 502–513, 2005.

[12] E. Lo, K. Y. Yip, K.-I. Lin, and D. W. Cheung, “Progressive skylining over Web-accessible Databases,” Data & Knowledge Engineering(DKE), 57(2):122–147, 2006.

[13] D. Papadias, Y. Tao, G. Fu, and B. Seeger, “Progressive Skyline Computation in Database Systems,” ACM TODS, 30(1):41–82, 2005.

[14] K.-L. Tan, P.-K. Eng, and B. C. Ooi, “Efficient Progressive Skyline Computation,” Proc. of VLDB conference, pp. 301–310, 2001.

[15] Y. Tao and D. Papadias. “Maintaining Sliding Window Skylines on Data Streams,” IEEE TKDE, 18(3), pp. 377-391, 2006.

[16] Y. Tao, X. Xiao, and J. Pei. “Efficient Skyline and Top-k Retrieval in Subspaces,” IEEE TKDE, 19(8), pp. 1072–1088 (2007).

[17] A. Vlachou, C. Doulkeridis, Y. Kotidis, and M. Vazirgiannis. “SKYPEER: Efficient Subspace Skyline Computation over Distributed Data,” Proc. of ICDE, pp. 416–425, 2007.

[18] A. Vlachou, C. Doulkeridis, and Y. Kotidis, “Angle-based Space Partitioning for Efficient Parallel Skyline Computation,” Proc. of SIGMOD, pp. 227-238, 2008.

[19] P. Wu, C. Zhang, Y. Feng, B. Y. Zhao, D. Agrawal, and A. E. Abbadi, “Parallelizing Skyline Queries for Scalable Distribution,” Proc. of EDBT, pp. 112-130, 2002.

[20] P. Wu, D. Agrawal, Ö. Egecioglu, and A. E. Abbadi, “Deltasky: Optimal Maintenance of Skyline Deletions without Exclusive Dominance Region Generation,” Proc. of ICDE, pp. 486-495, 2007.

[21] T. Xia, and D. Zhang, “Refreshing the Sky: The Compressed Skycube with
Efficient Support for Frequent Updates,” Proc. of SIGMOD, pp. 491-502, 2006.

[22] M. L. Yiu, and N. Mamoulis, “Efficient Processing of Top-k Dominating Queries on Multi-dimensional Data,” Proc. of VLDB conference, pp. 483–494, 2007.