臺灣博碩士論文加值系統

天際線查詢在以喜好為基底的資料分析中是一種高效率的工具,並且在資料庫的領域中吸引了越來越多的關注。 給定一擁有 d 個維度的物體集合 D, 天際線查詢將從D 中全面檢索, 找出不能被其它物體所支配的物體。 在本篇論文中 , 我們研究如何在道路網路上處理天際線查詢的問題,而在查詢的處理過程中將考慮物體之間的道路距離。 不同於以往的相關研究 , 我們的研究著重在連續地以距離為基底的天際線查詢處理。 我們提出兩種新穎且重要的查詢類型 , 其名稱分別為連續地 d 距離範圍內的天際線查詢以及連續地 k 個最近鄰居天際線查詢。 為了有效地在道路網路上處理這兩種查詢, 我們首先設計了網格索引來管理道路網路以及物體集合的資訊,然後發展了數個結合網格索引的演算法來找出查詢結果。 最後 , 我們執行了詳盡的實驗結果來證明我們提出方法俱有有效力及有效性。

The skyline query is an efficient tool for preference-based data analysis and attracts more attention than ever in the database community. Given a set of d-dimensional objects D, a skyline query retrieves all objects from D, which cannot be dominated by any others in D. In this paper, we investigate how to process the skyline query in road network, where the road distance between objects needs to be considered in query processing. Different from the previous related works, our work focuses on processing the continuous distance-based skyline query. We present two novel and important query types, named the Continuous d"-Skyline Query (Cd"-SQ for short) and the Continuous k nearest neighbor-Skyline Query (Cknn-SQ for short). To efficiently process the Cd"-SQ and Cknn-SQ in road network, we first design a grid index to manage the information of road network and objects, and then develop several algorithms combined with the grid index to determine the query result. Finally, we conduct a comprehensive set of experiments to demonstrate the effectiveness and the effciency of the proposed approaches.

Contents
Table of Contents iv
Table of Figures vi
Table of Tables viii
1 Introduction 1
2 Related Work 7
2.1 Traditional skyline queries.......................... 7
2.2 Skyline queries in road networks....................... 8
3 Data Structures and Grid Index 10
4 Query processing 13
4.1 Processing techniques for Cd"-SQ...................... 13
4.1.1 Cd"-SQP algorithm.......................... 14
4.1.2 Cd"-SQP+ algorithm......................... 18
4.2 Processing techniques for Cknn-SQ..................... 20
4.2.1 Cknn-SQP algorithm......................... 21
4.2.2 Cknn-SQP+ algorithm........................ 26
5 Performance Evaluation 28
5.1 Experimental Settings............................ 28
5.2 E?ect of number of grid cells......................... 30
iv5.3 Performance of the Cd"-SQP algorithm................... 31
5.3.1 E?ect of number of objects...................... 32
5.3.2 E?ect of number of attributes.................... 32
5.3.3 E?ect of query path length...................... 33
5.3.4 E?ect of d" range........................... 34
5.4 Performance of the Cknn-SQP algorithm.................. 34
5.4.1 E?ect of number of objects...................... 35
5.4.2 E?ect of number of attributes.................... 36
5.4.3 E?ect of query path length...................... 36
5.4.4 E?ect of attribute distribution.................... 37
5.4.5 E?ect of number of NNs....................... 38
5.5 Optimal algorithm.............................. 38
5.5.1 Post-optimal analysis......................... 38
6 Conclusions and Future Work 40
Bibliography 41

[1] S. Borzsonyi, D. Kossmann, and K. Stocker, “The skyline operator, in 17th International Conference on Data Engineering, pp. 421–430, 2001.
[2] J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, “Skyline with presorting, in Nineteenth International Conference on Data Ingineering, pp. 717–719, 2003.
[3] B. Jiang and J. Pei, “Online interval skyline queries on time series, in International Conference on Data Engineering, pp. 1036–1047, March 2009.
[4] W. Jin, A. K. H. Tung, M. Ester, and J. Han, “On efficient processing of subspace skyline queries on high dimensional data, in International Conference on Scientific and Statistical Database Management, 2007.
[5] D. Kossmann, F. Ramsak, and S. Rost, “Shooting stars in the sky: an online algorithm for skyline queries, in Proceedings of the VLDB Conference, 2002.
[6] X. Lin, Y.Yuan, Q. Zhang, and Y. Zhang, “Selecting stars: the k most representative skyline operator, in International Conference on Data Engineering, pp. 86–95,2007.
[7] J. Lee, G. W. You, and S. W. Hwang, “Personalized top-k skyline queries in high-dimensional space, in Information System, pp. 45–61, 2009.
[8] D. Papadias, Y. Tao, G. Fu, and B. Seeger, “An optimal and progressive algorithm for skyline queries, in ACM SIGMOD, pp. 467–478, 2003.
[9] N. Sarkas, G. Das, N. Koudas, and A. K. H. Tung, “Categorical skylines for streaming data, in ACM SIGMOD, pp. 239–250, 2008.41BIBLIOGRAPHY 42
[10] K.-L. Tan, P.-K. Eng, and B. C. Ooi, “Efficient progressive skyline computation, in International Conference on Very Large Data Bases, pp. 301–310, 2001.
[11] Y. Tao, X. Xiao, and J. Pei, “Subsky: efficient computation of skylines in sub-spaces, in IEEE International Conference on Data Engineering, 2006.
[12] K. Deng, X. Zhou, and H. T. Shen, “Multi-source skyline query processing in roadnetworks, in 23rd International Conference on Data Engineering, pp. 796–805,2007.
[13] K. Mouratidis, Y. Lin, and M. L. Yiu, “Preference queries in large multi-cost transportation networks, in International Conference on Data Engineering, 2010.
[14] M. Schubert, M. Renz, and H. Kriegel, “Route skyline queries: A multi-preference path planning approach, in International Conference on Data Engineering, 2010.
[15] L. Zou, L. Chen, M. T. Ozsu, and D. Zhao, “Dynamic skyline queries in large graphs, in International Conference on Database Systems for Advanced Applications, 2010.
[16] E. W. Dijkstra, “A note on two problems in connection with graphs, Numeriche Mathematik, vol. 1, pp. 269–271, 1959.
[17] R. Kung, E. Hanson, Y. Ioannidis, T. Sellis, L. Shapiro, and M. Stonebraker, “Heuristic search in data base system, in Proceedings of the International Workshop on Expert Database Systems, pp. 537–548, 1986.
[18] I. Bartolini, P. Ciaccia, and M. Patella, “Efficient sort-based skyline evaluation, ACM TODS, vol. 33, no. 4, pp. 1–45, 2008.
[19] X. Lin, Y. Yuan, W. Wangnicta, and H. Lu, “Stabbing the sky: Efficient skyline computation over sliding windows, in International Conference on Data Engineering, 2005.
[20] M. Morse, J. Patel, and W. Grosky, “Efficient continuous skyline computation, in Information System, pp. 3411–3437, 2007.BIBLIOGRAPHY 43
[21] Y. Tao and D. Papadias, “Maintaining sliding window skylines on data streams, IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 2, pp. 377–391, 2006.
[22] W. Zhang, X. Lin, Y. Zhang, W. Wang, and J. X. Yu, “Probabilistic skyline operator over sliding windows, in IEEE International Conference on Data Engineering, pp. 1060–1071, Washington, DC, USA, 2009.
[23] Z. Huang, B. O. H. Lu, and A. Tung, “Continuous skyline queries for moving objects, IEEE Transactions on Knowledge and Data Engineering, vol. 18, pp. 1645–1658, December 2006.
[24] M. Sharifzadeh and C. Shahabi, “The spatial skyline queries, in International Conference on Very Large Data Bases, pp. 751–762, 2006.
[25] H.-P. Kriegel, M. Renz, and M. Schubert, “Route skyline queries: A multi-preference path planning approach, in International Conference on Data Engineering, 2010.
[26] http://www.rtreeportal.org.
[27] http://www.cs.fsu.edu/~lifeifei/