臺灣博碩士論文加值系統

隨著無線網路的發展，越來越多不同的行動網路服務產生。其中，近年來常見與被廣泛運用的當屬天際線查詢。此論文針對新型態的容忍型天際線查詢，進行深入且詳細的研究，並提出一個基於網格的容忍型天際線查詢機制。所謂容忍型天際線查詢，即是當進行天際線查詢時，允許使用者根據個人偏好，將傳統pareto dominance的嚴格限制予以適度地放鬆，此舉可以放寬查詢結果組合，也更反映真實的應用情形。研究中，我們提出了利用網格環境的特性，能有效率地將傳統pareto-based dominance的關係，巧面的轉換成適合容忍型天際線查詢的運作。論文中也進行了多種不同的環境模擬，來評估與分析所提出的方法之效能與可行性。

This thesis introduces a new grid-based approach to solve tolerance-based skyline queries. Tolerance-based skyline queries is relatively new problem where the notion of tolerance margin is introduced previously as user preferences for the skyline query, which also serves to relax the rigidness of the classic skyline. The properties of the tolerance-based dominance relation is reviewed and investigated in this thesis. In particular, the relationship between traditional pareto-dominance and tolerance-based dominance relations is studied in depth. We then exploit this relationship along with grid properties to present an efficient grid-based scheme for processing a tolerance-based skyline with arbitrary tolerance tuple. Our algorithm essentially converts the tolerance-based skyline query processing operation into simple pareto-based dominance checking over grid space. Extensive experiments have been conducted to evaluate the performance of the proposed method.

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . . . .ii
Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . .v
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . vi
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Skyline Query . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Research Motivations . . . . . . . . . . . . . . . . . . . . . .3
1.3 Thesis Objectives . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . 6
2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Tolerance-Based Skyline Query Problem . . . . . . . . . . . . . . 10
3.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . .10
3.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . 13
3.2.2 Relationship Between Pareto and Tolerance-Based Dominance . . 16
4 Proposed Solution . . . . . . . . . . . . . . . . . . . . . . . .20
4.1 Overview of The Proposed Algorithm . . . . . . . . . . . . . . . 20
4.2 First Step : Grid Marking . . . . . . . . . . . . . . . . . . . .21
4.3 Second Step : Grid Traversing . . . . . . . . . . . . . . . . . .25
5 Performance Evaluation. . . . . . . . . . . . . . . . . . . . . . .27
5.1 Simulation Settings . . . . . . . . . . . . . . . . . . . . . . .27
5.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . 28
5.2.1 CPU Time vs. Data Size . . . . . . . . . . . . . . . . . . . . 28
5.2.2 CPU Time vs Dimensionality . . . . . . . . . . . . . . . . . . 29
5.2.3 CPU Time vs Maximum Tolerance Value . . . . . . . . . . . . . .31
5.2.4 CPU Time vs Grid Extent . . . . . . . . . . . . . . . . . . . .33
5.2.5 Memory Usage . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2.6 Maintenance Cost . . . . . . . . . . . . . . . . . . . . . . . 34
6 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . 36

[1] Wikipedia: Google now. Website, 07 2015.
[2] W.-T. Balke and U. Gntzer. Efficient skyline queries under weak pareto dominance. In Proc. Of The IJCAI-05 Multidisciplinary Workshop On Advance In Preference Handling (PREFERENCE), page 1, 2005.
[3] K. Benouaret, D. Benslimane, and A. Hadjali. On the use of fuzzy dominance for computing service skyline based on qos. In Proceedings of the 2011 IEEE International Conference on Web Services, ICWS '11, pages 540-547, Washington, DC, USA, 2011. IEEE Computer Society.
[4] S. Borzsony, D. Kossmann, and K. Stocker. The skyline operator. In Proc. Int'l Conf. Data Engineering (ICDE), pages 421-430, 2001.
[5] P. Bosc, A. Hadjali, and O. Pivert. On possibilistic skyline queries. In H. Chris tiansen, G. De Tr, A. Yazici, S. Zadrozny, T. Andreasen, and H. Larsen, editors, Flexible Query Answering Systems, volume 7022 of Lecture Notes in Computer Science, pages 412-423. Springer Berlin Heidelberg, 2011.
[6] D. E. Campbell and R. Nagahisa. A foundation for pareto aggregation. Journal of Economic Theory, 64(1):277 - 285, 1994.
[7] J. Chai, E. W. T. Ngai, and J. N. K. Liu. Dynamic tolerant skyline operation for decision making. Expert Syst. Appl., 41(15):6890-6903, Nov. 2014.
[8] J. Chomicki, P. Godfrey, J. Gryz, and D. Liang. Skyline with presorting. In Proc. Int'l Conf. Data Engineering (ICDE), pages 717-719, 2003.
[9] T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson. Introduction to Algo- rithms. McGraw-Hill Higher Education, 2nd edition, 2001.
[10] A. Das Sarma, A. Lall, D. Nanongkai, R. J. Lipton, and J. Xu. Representative skylines using threshold-based preference distributions. In Proceedings of the 2011 IEEE 27th International Conference on Data Engineering, ICDE '11, pages 387-398. IEEE Computer Society, 2011.
[11] R. Fagin. Combining fuzzy information from multiple systems (extended abstract). In Proc. ACM SIGACT-SIGMOD-SIGART Symp. Principles of Database Systems (PODS), pages 216-226, 1996.
[12] R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. In Proc. ACM SIGMOD-SIGACT-SIGART Symp. on Principles of Database Systems (PODS), pages 102-113, 2001.
[13] M. Goncalves and L. Tineo. Fuzzy dominance skyline queries. In R.Wagner, N. Revell, and G. Pernul, editors, Database and Expert Systems Applications, volume 4653 of Lecture Notes in Computer Science, pages 469-478. Springer Berlin Heidelberg, 2007.
[14] M. Goncalves and M.-E. Vidal. Preferred skyline: A hybrid approach between sqlf and skyline. In Proceedings of the 16th International Conference on Database and Expert Systems Applications, DEXA'05, pages 375-384. Springer-Verlag, 2005.
[15] A. Hadjali, O. Pivert, and H. Prade. On different types of fuzzy skylines. In Foun dations of Intelligent Systems, volume 6804 of Lecture Notes in Computer Science, pages 581-591. Springer Berlin Heidelberg, 2011.
[16] K. Hose, C. Lemke, and K.-U. Sattler. Processing relaxed skylines in pdms using distributed data summaries. In Proceedings of the 15th ACM International Conference on Information and Knowledge Management, CIKM '06, pages 425-434, New York, NY, USA, 2006. ACM.
[17] W. Jin, J. Han, and M. Ester. Mining thick skylines over large databases. In Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, PKDD '04, pages 255-266. Springer-Verlag New York, Inc., 2004.
[18] M. E. Khalefa, M. F. Mokbel, and J. J. Levandoski. Skyline query processing for incomplete data. In Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, ICDE '08, pages 556-565. IEEE Computer Society, 2008.
[19] M. E. Khalefa, M. F. Mokbel, and J. J. Levandoski. Skyline query processing for uncertain data. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management, CIKM '10, pages 1293-1296. ACM, 2010.
[20] D. Kim, H. Im, and S. Park. Computing exact skyline probabilities for uncertain databases. Knowledge and Data Engineering, IEEE Transactions on, 24(12):2113- 2126, Dec 2012.
[21] K. C. 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, June 2010.
[22] X. Lin, J. Xu, and H. Hu. Range-based skyline queries in mobile environments. IEEE Trans. Knowledge and Data Eng., PrePrints, 2011.
[23] X. Lin, Y. Yuan, W. Wang, and H. Lu. Stabbing the sky: efficient skyline computation over sliding windows. In Proc. Int'l Conf. Data Engineering (ICDE), pages 502-513, 2005.
[24] X. Liu, D. Yang, M. Ye, and W. Lee. U-skyline: A new skyline query for uncertain databases. IEEE Trans. Knowledge and Data Eng., PrePrints, 2012.
[25] X. Liu, D.-N. Yang, M. Ye, and W.-C. Lee. U-skyline: A new skyline query for uncertain databases. Knowledge and Data Engineering, IEEE Transactions on, 25(4):945-960, April 2013.
[26] H. Lu, C. S. Jensen, and Z. Zhang. Flexible and efficient resolution of skyline query size constraints. IEEE Trans. on Knowl. and Data Eng., 23(7):991-1005, July 2011.
[27] D. Papadias, Y. Tao, G. Fu, and B. Seeger. An optimal and progressive algorithm for skyline queries. In Proc. ACM SIGMOD Int'l Conf. Management of Data (SIGMOD), pages 467-478, 2003.
[28] D. Papadias, Y. Tao, G. Fu, and B. Seeger. Progressive skyline computation in database systems. ACM Trans. Database Syst., 30(1):41-82, Mar. 2005.
[29] A. N. Papadopoulos, A. Lyritsis, A. Nanopoulos, and Y. Manolopoulos. Domination mining and querying. In Data Warehousing and Knowledge Discovery, volume 4654 of Lecture Notes in Computer Science, pages 145-156. Springer Berlin Heidelberg, 2007.
[30] J. Pei, B. Jiang, X. Lin, and Y. Yuan. Probabilistic skylines on uncertain data. In Proceedings of the 33rd International Conference on Very Large Data Bases, VLDB '07, pages 15-26. VLDB Endowment, 2007.
[31] B. J. Santoso and G.-M. Chiu. Tolerance-based skyline queries (unpublished).
[32] B. J. Santoso and G.-M. Chiu. Close dominance graph: An efficient framework for answering continuous top- k dominating queries. Knowledge and Data Engineering, IEEE Transactions on, 26(8):1853-1865, Aug 2014.
[33] K.-L. Tan, P.-K. Eng, and B. C. Ooi. Efficient progressive skyline computation. In Proc. Int'l Conf. Very Large Data Bases (VLDB), pages 301-310, 2001.
[34] Y. Tao, L. Ding, X. Lin, and J. Pei. Distance-based representative skyline. In Proc. Int'l Conf. Data Engineering (ICDE), pages 892-903, 2009.
[35] L. Tian, L. Wang, P. Zou, Y. Jia, and A. Li. Continuous monitoring of skyline query over highly dynamic moving objects. In Proceedings of the 6th ACM International Workshop on Data Engineering for Wireless and Mobile Access, MobiDE '07, pages 59-66, New York, NY, USA, 2007. ACM.
[36] A. Vlachou, C. Doulkeridis, Y. Kotidis, and M. Vazirgiannis. Skypeer: Efficient subspace skyline computation over distributed data. In Proc. Int'l Conf. Data Engineering (ICDE), pages 416-425, Apr. 2007.
[37] M. Voorneveld. Characterization of pareto dominance. Operations Research Letters, 31(1):7 - 11, 2003.
[38] S. Wang, Q. Vu, B. Ooi, A. Tung, and L. Xu. Skyframe: a framework for skyline query processing in peer-to-peer systems. The VLDB Journal, 18(1):345-362, 2009.
[39] T. Xia, D. Zhang, and Y. Tao. On skylining with
exible dominance relation. In Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on, pages 1397-1399, April 2008.
[40] Q. Zhang, P. Ye, X. Lin, and Y. Zhang. Skyline probability over uncertain preferences. In Proceedings of the 16th International Conference on Extending Database Technology, EDBT '13, pages 395-405. ACM, 2013.
[41] Z. Zhang, H. Lu, B. C. Ooi, and A. K. Tung. Understanding the meaning of a shifted sky: A general framework on extending skyline query. The VLDB Journal, 19(2):181-201, Apr. 2010.
[42] K. Zheng, X. Zhou, P. C. Fung, and K. Xie. Spatial query processing for fuzzy objects. The VLDB Journal, 21(5):729-751, Oct. 2012.