Skyline 和dominance relationship 的分析在商業的應用上越來越受到重視。在商業應用的情境中，資料空間中的一個點，就代表了一個廠商的產品。若廠商的產品為一個skyline point，那代表本產品是一個具有競爭力的產品。更精確地說，代表了這個產品在市場上，並沒有競爭對手。在本論文中，我們提出了「藉由客戶偏好和成本限制搜尋天際線」的問題。在本問題中，我們探討了以廠商的角度來看，資料處理的技術如何幫助廠商找出資料空間中具有足夠利潤，有競爭力，並且能對使用者有足夠足引力的產品。給一個客戶偏好的集合和成本限制[costL,costU]，我們提出了一系列的演算法，幫助廠商尋找產品空間中符合成本限制（如此一來才有利潤），以及能吸引最多使用者的skyline 產品。在論文中，我們詳細地定義了此一問題，提出了設計演算法的原理、pruning 的技巧，以及相關的理論。此外，我們也證明了演算法以及相關輔助定理的正確性。最後，我們做了完整的實驗評估而且展示了演算法的效能。

The importance of skyline and dominance relationship analysis has been well recognized in multicriteria decision-making applications. In this paper, we propose the problem of “Finding Skyline with Customer Preferences and Cost Constraints”, which utilizes the concept of dominance for business analysis from a microeconomic perspective. Our problem aims to discover the dominance relationship between products and potential customers. Given a set of customer preferences, we want to help the company to design set of competitive products so that the products can satisfy as many customer requirements as possible and the cost of producing the products is within a specified threshold. By “competitive products” we mean that the products cannot be dominated by other products in the market. We formally define the problem and discuss the difficulty of the problem. We also present the foundation and the intuition of our pruning methods. Then we proposed three efficient algorithms that utilize our pruning methods to address the problem. In addition, we also prove the correctness of our proposed algorithms. Finally, we conduct a thorough experimental evaluation that demonstrates the efficiency of our proposed algorithms.

[1]C. Li, B. C. Ooi, A. K. H. Tung, and S. Wang, “DADA: A data cube for dominant relationship analysis,” in SIGMOD, pp. 659-670, 2006.
[2]Z. Zhang, L. Lakshmanan, and A. K.H. Tung, “On domination game analysis for microeconomic data mining,” in TKDD, 2(4), 2009.
[3]Y.Peng, and C.-W. Wong, “Finding Competitive price,” in the proceedings of the 21st ACM SIGSPATIAL, pp. 144-153, 2013.
[4]H Lu, and C. S. Jensen, “Upgrading uncompetitive products economically,” in ICDE, pp. 977-988, 2012.
[5]Q. Wan, R. C.-W. Wong, and Y. Peng, “Finding top-k profitable products,” in Proceedings of ICDE, pp. 1055-1066, 2011.
[6]Chen-Yi Lin, Jia-Ling Koh, and A. L. P. Chen, “Determining k-most requirementing products with the maximum expected number of total customers,” IEEE Transactions on Knowledge and Data Engineering, vol. 25, no. 8, pp. 1732-1747, 2013.
[7]Q. Wan, R. C.-W. Wong, I. F. Ilyas, M. T. Ozsu, and Y. Peng, “Creating competitive products,” in VLDB, vol. 2(1), pp. 898-909, 2009.
[8]Kleinbega, J., Papadimitriou, C. and Raghavan, P., “A microeconomic view of data mining,” in Data Mining Knowledge Discovery, vol. 2(4), pp. 311-322, 1998.
[9]Osborne, M. J. and Rubinstein, A., “A course in game theory,” the MIT press, 1994.
[10]S. Borzsonyi, D. Kossmann, and K. Stocker, “The skyline operator,” in ICDE, pp. 421-430, 2001.
[11]K.-L, Tan, P. Eng, and B. Ooi, “Efficient progressive skyline computation,” in VLDB, pp. 301-310, 2001.
[12]Scott Anthony, Mark W. Joshson, Joseph V. Sinfield, and Elizabeth J. Altman, “The innovator’s Guide to Growth,” in CommonWealth Magazine, 2008.
[13]X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang, “Selecting stars: the k most representative skyline operator,” in Proceedings of the 23rd International Conference on Data Engineering, pp. 86-95, 2007.
[14]J. L. B. et al, “On the average number of maxima in a set of vectors and applications,” in Journal of ACM, pp. 25(4), 1978.
[15]J. L. B. et al, “Fast linear expected-time algorithms for computing maxima and convex hulls,” in SODA, pp.179-187, 1990.
[16]D. Kossmann, F. Ramask, and S. Rost, “Shooting star in the sky: An online algorithm for skyline queries,” in VLDB, pp. 275-286, 2002.
[17]D. Papadias, Y. Tao, G. Fu, and B. Seeger, “Progressive skyline computation in database systems,” in ACM Transactions on Database Systems, vol. 30, no. 1, pp. 41-82, 2005.