臺灣博碩士論文加值系統

Skyline query processing can be used on multi-criteria decisions and user preference applications so that extensive studies have been conducted in recent years. A skyline query returns the set of tuples that are not dominated by others on all dimensions in a multi-dimensional database. A user thus may make effective decisions with the set of interesting tuples, called the skyline. Nevertheless, the number of skyline tuples will increase as the number of dimensions increases because fewer tuples might be dominated by a tuple on all dimensions. Instead of returning all the skyline tuples for users, a top-k skyline query retrieves only tuples whose rank is no greater than k. Top-k skyline queries hence become the focus of skyline query researches. In addition, not all users are interested in the skyline tuples for all dimensions, especially for a database of high dimensionality. Different users may have different preferred combinations of dimensions. A subspace skyline is intended to retrieve the skyline tuples with respect to a specified subset of interested dimensions. Most studies on subspace skyline pre-computes and stores all combinations of the subspace skylines for fast responses of the subspace queries. Such a solution, however, is infeasible for databases of high dimensionality since there are an exponential number of combinations.
To our knowledge, no studies have been proposed to deal with top-k queries integrated with online computations of subspace skyline queries for high-dimensional databases. In this thesis, we propose the TF-Rank algorithm and the TS-Rank algorithm, respectively, to efficiently retrieve the top-k skyline tuples on all dimensions and on any specified subspace of dimensions. Both algorithms use a dominance table for quick computations of the ranked top-k tuples. Moreover, the rank of a tuple is calculated by a scoring function which normalizes the domains of dimensions for fair computations of relative scores for the incomparable skyline tuples. Our experiments indicate that the scoring function is effective in comparison to some previous ranking algorithms of high complexity. Extensive experiments show that the proposed algorithms may efficiently discover skyline tuples, both in the full-space and in the subspaces.

誌謝 i
摘要 ii
Abstract iii
Table of Contents iv
List of Figures vi
List of Tables vii
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 2
1.3 Problem Definitions 6
1.4 Research Objectives 8
1.5 Thesis Organization 9
Chapter 2 Related Work 10
2.1 Conventional Skyline Query 10
2.1.1 No Index Structure 10
2.1.2 Index Structure 13
2.2 Subspace Skyline Query 17
2.2.1 SKYCUBE 17
2.2.2 SUBSKY 18
2.2.3 SS-query 19
2.3 Top-k and Ranked Skyline Query 20
2.3.1 Skyline Frequency 20
2.3.2 ADNRA Algorithm 21
2.3.3 SKYRANK 22
Chapter 3 Proposed Algorithms 23
3.1 Preliminaries 23
3.2 Construction of D-table 24
3.3 Relative Score Function 27
3.4 Top-k Full Space Skyline with Ranking 29
3.4.1 Example for TF-Rank 31
3.4.2 The TF-Rank Algorithm 32
3.5 Top-k Subspace Skyline with Ranking 33
3.5.1 Example for TS-Rank 34
3.5.2 The TS-Rank Algorithm 37
Chapter 4 Experimental Results 38
4.1 Configurations of Experiments 38
4.2 Datasets 38
4.3 Ranking Results on Real Dataset 39
4.4 Execution Time of Ranking on Full Space (TF-Rank) 41
4.4.1 Execution Time of Varying Data Size on Full Space 41
4.4.2 Execution Time of Varying Dimensionality on Full Space 42
4.4.3 Execution Time of Varying Top-k Skyline Tuples 42
4.5 Execution Time of Ranking on Subspace (TS-Rank) 43
4.5.1 Execution Time of Varying Data Size on Subspace 43
4.5.2 Execution Time of Varying Dimensionality on Subspace 45
4.5.3 Execution Time of Varying Top-k Subspace Skyline Tuples 46
Chapter 5 Conclusions 48
5.1 Contributions 48
5.2 Future Work 49
References 50

[1]Stephan Börzsönyi , Donald Kossmann , and Konrad Stocker, “The Skyline Operator,” Proceedings of International Conference on Data Engineering (ICDE), pp. 421–430, 2001.
[2]Ilaria Bartolini, Paolo Ciaccia and Marco Patella, “The Skyline of a Probabilistic Relation,” IEEE Transactions on Knowledge and Data Engineering (TKDE), Vol.25, No.7, pp. 1656–1669, 2013.
[3]Tassadit Bouadi, Marie-Odile Cordier, and Rene Quiniou, “Incremental Computation of Skyline Queries with Dynamic Preferences,” Proceedings of the International Conference on Database and Expert Systems Applications (DEXA), pp. 219-233, 2012.
[4]Chee-Yong Chan , H.V. Jagadish , Kian-Lee Tan , Anthony K. H. Tung , and Zhenjie Zhang, “On High Dimensional Skylines,” Proceedings of the International Conference on Extending Database Technology (EDBT), pp. 478-495, 2006.
[5]Chee-Yong Chan, H. V. Jagadish, Kian-Lee Tan, Anthony K.H. Tung, and Zhenjie Zhang, “Finding k-Dominant Skylines in High Dimensional Space,” Proceedings of the ACM International Conference on Management of data (SIGMOD), pp. 503-514, 2006.
[6]Jan Chomicki, Parke Godfrey, Jarek Gryz, and Dongming Liang, “Skyline with presorting,” Proceedings of International Conference on Data Engineering (ICDE), pp. 717–719, 2003.
[7]Ronald Fagin, Amnon Lotem, and Moni Naor, “Optimal aggregation algorithms for middleware,” Proceedings of the ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pp. 601-612, 2001.
[8]Marlene Goncalves and Maria-Esther Vidal: Reaching the Top of the Skyline, “An Efficient Indexed Algorithm for Top-k Skyline Queries,” Proceedings of the International Conference on Database and Expert Systems Applications (DEXA), pp. 471-485, 2009.
[9]Zhenqiang Gong, Guang-Zhong Sun, Jing Yuan, and Yanjing Zhong, “Efficient Top-k Query Algorithm Using K-Skyband Partition,” Proceedings of the International Conference on Scalable Information Systems (Infoscale), pp. 288-305, 2009.
[10]Wen Jin and Jignesh M Patel, “Efficient and Generic Evaluation of Ranked Queries,” Proceedings of the ACM International Conference on Management of data (SIGMOD), pp. 601-612, 2011.
[11]Wen Jin, Anthony K.H. Tung, Martin Ester, and Jiawei Han, “On Efficient Processing of Subspace Skyline Queries on High Dimensional Data,” Proceedings of International Conference on Scientific and Statistical Database Management, pp. 1-10, 2007.
[12]H. T. Kung, F. Luccio, and F. P. Preparata, “On finding the maxima of a set of vectors,” Journal of the ACM, Vol. 22, No. 4, pp.469–476, 1975.
[13]Donald Kossmann, Frank Ramsak, and Steffen Rost, “Shooting stars in the sky: an online algorithm for skyline queries,” Proceedings of International Conference on Very Large Data Bases (VLDB), pp. 275–286, 2002.
[14]Yang Lu, Jiakui Zhao, Lijun Chen, Bin Cui, and Dongqing Yang, “Effective Skyline Cardinality Estimation on Data Streams,” Proceedings of the International Conference on Database and Expert Systems Applications (DEXA), pp. 241-254, 2008.
[15]Weifa Liang, Baichen Chen and Jeffrey Xu Yu, “Energy-efficient skyline query processing and maintenance in sensor networks,” Proceedings of the International Conference on Information and Knowledge Management (CIKM), pp. 1471-1472, 2008.
[16]Jongwuk Lee, Gae-won You, and Seung-won Hwang, “Telescope: Zooming to Interesting Skylines,” Proceedings of the International Conference on Database Systems for Advanced Applications (DASFAA), pp. 539-550, 2007.
[17]Jongwuk Lee, Gae-won You, and Seung-won Hwang, “Personalized top-k skyline queries in high-dimensional space,” Information Systems, Vol. 34, No. 1, pp. 45-61, 2009.
[18]Yu Won Lee, Ki Yong Lee, and Myoung Ho Kim, “Efficient processing of multiple continuous skyline queries over a data stream,” Information Sciences, pp. 316-337, 2013.
[19]Jongwuk Lee, Gae-won You, Seung-won Hwang, Joachim Selke, and Wolf-Tilo Balke, “Interactive Skyline Queries,” Information Sciences, pp. 18-35, 2012.
[20]Dimitris Papadias, Yufei Tao, Greg Fu, and Bernhard Seeger, “An Optimal and Progressive Algorithm for Skyline Queries,” Proceedings of the ACM International Conference on Management of data (SIGMOD), pp. 503-514, 2003.
[21]Jian Pei, Wen Jin, Martin Ester, and Yufei Tao, “Catching the best views of skyline: a semantic approach based on decisive subspaces,” Proceedings of International Conference on Very Large Data Bases (VLDB), pp. 253–264, 2005.
[22]Jian Pei, Bin Jiang, Xuemin Lin, and Yidong Yuan, “Probabilistic skylines on uncertain data,” Proceedings of International Conference on Very Large Data Bases (VLDB), pp. 15-26, 2007.
[23]Yohan J. Roh, Inchul Song, Joo Hyuk Jeon, Kyoung Gu Woo and Myoung Ho Kim, “Energy-Efficient Two-Dimensional Skyline Query Processing in Wireless Sensor Networks,” Proceedings of the International Conference on Consumer Communications and Networking Conference (CCNC), pp. 204-301, 2013.
[24]Kian-Lee Tan, Pin-Kwang Eng, and Beng Chin Ooi, “Efficient progressive skyline computation,” Proceedings of International Conference on Very Large Data Bases (VLDB), pp. 301–310, 2001.
[25]Kian-Lee Tan, Pin-Kwang Eng, and Beng Chin Ooi, “Indexing for progressive skyline computation,” Data &; Knowledge Engineering (DKE), Vol. 46, No. 2, pp.169–201, 2003.
[26]Yufei Tao, Xiaokui Xiao, and Jian Pei, “Efficient skyline and top-k retrieval in subspaces,” IEEE Transactions on Knowledge and Data Engineering (TKDE), Vol.19, No.8, 1072–1088, 2007.
[27]Yufei Tao and Dimitris Papadias, “Maintaining Sliding Window Skylines on Data Streams,” IEEE Transactions on Knowledge and Data Engineering (TKDE), Vol.18, No.3, 377–391, 2006.
[28]Akrivi Vlachou and Michalis Vazirgiannis, “Ranking the sky: Discovering the importance of skyline points through subspace dominance relationships,” Data &; Knowledge Engineering (DKE) , Vol. 69 , No. 9, pp.943–964,2010.
[29]Raymond Chi-Wing Wong, Ada Wai-Chee Fu, Jian Pei, Yip Sing Ho, Tai Wong, and Yubao Liu, “Efficient Skyline Querying with Variable User Preferences on Nominal Attribute,” Proceedings of International Conference on Very Large Data Bases (VLDB), pp. 1032-1043, 2008.
[30]Yuan, X. Lin, Q. Liu, W. Wang, J.X. Yu, and Q. Zhang, “Efficient Computation of the Skyline Cube,” Proceedings of International Conference on Very Large Data Bases (VLDB), pp. 241-252, 2005.
[31]Ying Zhang, Wenjie Zhang, Xuemin Lin, Bin Jiang, and Jian Pei, “Ranking uncertain sky: The probabilistic top-k skyline operator,” Information Sciences, pp. 898-915, 2011.
[32]Qing Zhang, Penjie Ye, Xuemin Lin, and Ying Zhang, “Skyline Probability over Uncertain Preferences,” Proceedings of the International Conference on Extending Database Technology, pp.395-405, 2013.