臺灣博碩士論文加值系統

天際線查詢因為其廣泛的應用在多準則決策與使用者喜好應用，所以近來受到相當多的關注。天際線查詢目的是找出在所有維度上沒有被其他資料點支配的資料點，稱之為天際線點，此查詢可以將沒有參考價值的資料刪除。然而，對於使用者來說，有興趣的天際線需要相對於使用者指定的資料來計算，這種查詢被稱之為動態天際線查詢。基於動態天際線查詢的想法，反向天際線是找出有哪些點將使用者指定的資料當成動態天際線點。如果使用者指定的資料被很多點當成動態天際線點，即代表使用者指定的資料被很多點感興趣。換句話說，使用者指定的資料點的反向天際線點越多，代表越受歡迎。
因此，反向天際線的查詢結果可以被產品供應商用來了解潛在的客戶，與其商品受歡迎的程度。在這篇論文中，我們提出一個演算法EquRanger去找出一個被選定維度在反向天際線查詢上對於參考點來說的等值區間。產品供應商可以選擇任何在這個維度上等值區間的值去取代參考點原有的值，新的參考點稱之為等值點。等值點的反向天際線集合與原來的參考點相同或者是原來的超集合。所以，產品提供者可以在沒有失去原本顧客的情形下根據新參考產品獲得利益。
此外，我們也提出了一個MaxRangeru演算法去找出每個維度最大值的組合。此演算法可以找出多維度的等值區間，利用多維度等值點可以獲得最大的利益。
大量的實驗表明本演算法可以在反向天際線計算上有效率的找出等值區間與最大的利潤。

Skyline queries are receiving much attention recently because of its wide applicability in multi-criteria decision-making and user-preference applications. A skyline query returns only the data objects, called skyline points, in a set that are not dominated by any other data object on all dimensions. Occasionally, the interested skyline needs to be computed with respect to a user-specified data point, such a query is referred to as a dynamic skyline query. Based on the idea of dynamic skyline queries, a reverse skyline query finds out the set of data points whose dynamic skyline contains the reference data point. The result of a reverse skyline query can be used by a provider to understand the potential customers, showing their interested products as data points, with respect to a reference product-point. In this thesis, we propose the EquRanger algorithm to find the equivalent range of a selected attribute for the reference point in a reverse skyline query. The provider may use any value in the equivalent range to substitute the original value for this attribute and obtain a new reference point, named equivalent point. Particularly, the reverse skyline of the equivalent point is the same set or a superset of the original reverse skyline. Thus, the provider may benefit from presenting the new reference product without losing any original potential customer. Furthermore, we also propose the MaxRanger algorithm to find out a combination of the maximum value for each attribute. The combination sets the attribute values of multiple domains altogether to generate a maximum profitable equivalent point. Extensive experiments show that the proposed algorithms may efficiently discover the equivalent ranges and maximum profitable equivalent points in reverse skyline computations.

誌謝 i
摘要 ii
Abstract iii
Table of Contents iv
List of Figures vi
List of Tables viii
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 3
1.3 Problem Statements 5
1.4 Research Objectives 11
1.5 Thesis Organization 12
Chapter 2 Related Work 13
2.1 Skyline Query 13
2.1.1 BNL Algorithm 13
2.1.2 DC Algorithm 14
2.1.3 SFS Algorithm 15
2.1.4 Bitmap Algorithm 16
2.1.5 Index Algorithm 17
2.1.6 NN Algorithm 18
2.1.7 BBS Algorithm 20
2.2 Dynamic Skyline Query 22
2.2.1 Cache-aware Algorithm 22
2.2.2 MDS Algorithm 23
2.3 Reverse Skyline Query 23
2.3.1 BBRS Algorithm 23
2.3.2 RSSA Algorithm 24
Chapter 3 Algorithms for Equivalent Range Computations 27
3.1 Algorithm Naïve_Find_Equivalent_Range 27
3.2 Algorithm Equivalent Range for Reverse Skylines 28
3.3 Algorithm Maximizing Range Value for Reverse Skylines 33
3.4 Complexity of EquRanger and Naïve Method 35
Chapter 4 Experimental Results 36
4.1 Data Sets 36
4.2 Varying Data Size 39
4.3 Varying Dimensions 49
4.4 Multi-dimensional Equivalent Range 52
4.5 Comparison with Naïve Method 53
Chapter 5 Conclusions 57
5.1 Contributions 57
5.2 Future Works 58
References 60

[1]S. Borzsonyi, D. Kossmann and K. Stocker, “The Skyline Operator,” Proceedings of the 17th International Conference on Data Engineering, pp. 421-430, 2001.
[2]J. Chomicki, P. Godfrey, J. Gryz and D. Liang. “Skyline with Presorting,” Proceedings of the 19th International Conference on Data Engineering, pp. 717-719, 2003.
[3]C. Y. Chan, H.V. Jagadish, K. L. Tan, Anthony K.H. Tung and Z. Zhang. “Finding k-Dominant Skylines in High Dimensional Space,” Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 503-514, 2006.
[4]L. Chen and X. Lian. “Dynamic Skyline Queries in Metric Spaces,” Proceedings of 11th International Conference on Extending Database Technology (EDBT), pp. 333-343, 2008.
[5]E. Dellis and B. Seeger. “Efficient Computation of Reverse Skyline Queries,” Proceedings of the 33rd International Conference on Very Large Data Bases, pp. 291-302, 2007.
[6]D. Kossmann, F. Ramsak and S. Rost. “Shooting Stars in the Sky: An Online Algorithm for Skyline Queries,” Proceedings of the 28th International Conference on Very Large Data Bases, pp. 275-286, 2002.
[7]X. Lian and L. Chen. “Reverse Skyline Search in Uncertain Databases,” ACM Transactions on Database Systems (TODS), Vol. 35, No. 1, 2010.
[8]M. D. Morse, J. M. Patel and H.V. Jagadish. “Efficient Skyline Computation over Low-Cardinality Domains,” Proceedings of the 33rd International Conference on Very Large Data Bases, pp. 267-278, 2007.
[9]D. Papadias, Y. Tao, G. Fu and B. Seeger. “Progressive Skyline Computation in Database Systems,” ACM Transactions on Database Systems, Vol. 30, No. 1, pp. 41-82, 2005.
[10]D. Papadias, Y. Tao, G. Fu and B. Seeger. “An Optimal and Progressive Algorithm for Skyline Queries,” Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pp. 467-478, 2003.
[11]D. Sacharidis, P Bouros and T. K. Sellis. “Caching Dynamic Skyline Queries,” Proceedings of the 20th International Conference on Scientific and Statistical Database Management, pp. 455-472, 2008.
[12]D. Skoutas, D. Sacharidis, A. Simitsis and Timos K. Sellis. “Serving the Sky: Discovering and Selecting Semantic Web Services through Dynamic Skyline Queries,” Proceedings of the 2nd IEEE International Conference on Semantic Computing (ICSC), pp. 222-229, 2008.
[13]I. Stojmenovic and M. Miyakawa. “An Optimal Parallel Algorithm for Solving the Maximal Elements Problem in the Plane,” Parallel Computing, Vol. 7, No. 1, pp. 249-251, 1988.
[14]K. L. Tan, P. K. Eng and B. C. Ooi. “Efficient Progressive Skyline Computation,” Proceedings of the 27th International Conference on Very Large Data Bases, pp. 301-310, 2001.
[15]W. C. Wang, E. T. Wang and A. L.P. Chen. “Dynamic skylines considering range queries,” Database Systems for Advanced Applications - 16th International Conference, pp.235-250, 2011.
[16]Y. Yuan, X. Lin, Q. Liu, W. Wang, J. X. Yu and Q. Zhang. “Efficient Computation of the Skyline Cube,” Proceedings of the 31st International Conference on Very Large Data Bases, pp. 241-252, 2005.
[17]L. Zhu, C. Li and H. Chen. “Efficient Computation of Reverse Skyline on Data Stream,” Proceedings of the 2nd International Joint Conference on Computational Sciences and Optimization, pp. 735-739, 2009.