臺灣博碩士論文加值系統

近來有越來越多的學者們著手於多條件查詢處理技術之研究。我們的研究主要使用了天際線查詢來找出多條件查詢的結果。給予一個具有多個維度的資料庫，這個查詢可以回傳所有不被「支配」（細節將於本論文中介紹）的資料點。本論文分為兩個部分。第一個部分介紹了三個過往執行天際線查詢或其應用時會遇到的困難。這些困難包含了資料庫中過多的資料量會嚴重影響天際線搜尋的執行效率、天際線搜尋無法針對資料庫中無法量化的維度進行查詢，以及執行子維度天際線搜尋時的低效率問題。第二個部分討論了如何將天際線搜尋應用至其他環境上，包含distributed client-server environment以及spatio-temporal database environment。這篇論文提出了一些新穎的方法來解決上述的問題。本論文所有提出來的演算法都會經由實驗模擬分析及驗證。實驗模擬結果則證實了我們所提出來的演算法確能有效處理天際線查詢及其延伸之查詢。

Multi-criteria searching technique has attracted a great deal of attention in recent years. In our work, we focus on the skyline queries and its extensions for evaluating such multi-criteria searching results. Given a set of data points in a multidimensional database, such queries return points that are not “dominated” (detailed in this thesis) by any other point. This thesis is divided into two parts. The first part introduces three problems that arise during the execution of a skyline query or its extension. They are the problems caused by the excessive quantity of data in databases, the inability of processing a skyline query in databases with unquantifiable dimensions, and the inefficiency of processing a subspace skyline query. The second part of the thesis addresses the issue of how a skyline query can be incorporated into new environments, including the distributed client-server environment and the spatio-temporal database environment. Novel solutions to these problems are presented in this thesis. All proposed algorithms are analyzed and simulated through extensive experiments. The results indicate that they are effective in supporting a skyline query and its applications mentioned in this thesis.

Chinese Abstract i
Abstract ii
List of Contents iv
List of Tables ix
List of Figures x
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Overview of the Dissertation 4
1.2.1 Neural Skyline Filter for Accelerating Skyline Search Algorithms 4
1.2.2 The σ-Neighborhood Skyline Queries 5
1.2.3 Depth-k skyline query for unquantifiable attributes in distributed systems 5
1.2.4 G-tree: A Novel Index Structure for Subspace Skyline Query 6
1.2.5 The Skyline Path Query with Aggregate Attributes 6
1.3 Organization of the Dissertation 7
Chapter 2 Neural Skyline Filter for Accelerating Skyline Search Algorithms 8
2.1 Introduction 8
2.2 Related work 12
2.2.1 Block nested loop (BNL) 12
2.2.2 Divide-and-conquer (DAC) 13
2.2.3 Sort filter skyline (SFS) 14
2.2.4 Branch-and-bound skyline (BBS) 15
2.2.5 Neural Networks 17
2.3 Naïve skyline filter 19
2.3.1 Filtering Point Sieving Phase 20
2.3.2 Filtering Phase 20
2.3.3 Efficiency of the Naïve Skyline Filter 22
2.4 Neural skyline filter (NuSF) 23
2.4.1 Structure of the Neural Skyline Filter 24
2.4.2 Neural Skyline Filter Construction Algorithm 27
2.4.2.1 Training Data Generation Phase 28
2.4.2.2 Neural Skyline Filter Initialization Phase 31
2.4.2.3 Neural Skyline Filter Training Phase 33
2.4.3 Neural Skyline Filter Query Processing Mechanism 35
2.4.4 Universal Approximation of the Neural Skyline Filter 36
2.4.5 Brief Summary 38
2.5 Featured neural skyline filter (FNuSF) 38
2.5.1 Structure of the Featured Neural Skyline Filter 40
2.5.2 Construction Algorithm for Featured Neural Skyline Filter 42
2.5.3 Mechanism of Featured Neural Skyline Filter for Processing Queries 42
2.5.4 Brief Summary 43
2.6 Completeness of the skyline points 43
2.7 Performance evaluation 46
2.7.1 Comparisons of the SNF, the NuSF, and the FNuSF 47
2.7.2 Completeness of the Skyline Points 55
2.7.3 Using FNuSF as a Filter for Skyline Search 57
2.7.3.1 Proper Number of Hidden Neurons in FNuSF 57
2.7.3.2 Performance of Skyline Search Using the FNuSF 58
2.7.3.3 Time cost of operating the FNuSF 64
2.8 Summary 67
Chapter 3 The σ-Neighborhood Skyline Queries 68
3.1 Introduction 68
3.2 Problem Definition 72
3.3 An R-tree-based method for Σ-N skyline queries 74
3.3.1 Spatial relationships between an σ-N skyline region and an MBR or point of an R-tree 75
3.3.2 Rσ-N Algorithm 76
3.4 An M+-tree-based method for Σ-N skyline queries 83
3.4.1 M+-tree 84
3.4.2 The merits of using the M+-tree in σ-N skyline queries 87
3.4.3 The Mσ-N algorithm 89
3.4.3.1 Inheritance-based pruning mechanism 89
3.4.3.2 Summation-checking mechanisms 91
3.4.3.3 Inequality-based pruning mechanisms 96
3.4.3.4 An example 97
3.5 Simulation 101
3.5.1 Finding a suitable σ for different datasets 102
3.5.2 Effect of dimensionality 105
3.5.3 Effect of Cardinality 107
3.5.4 Effect of σ 108
3.6 Summary 110
Chapter 4 Depth-k skyline query for unquantifiable attributes in distributed systems 111
4.1 Introduction 111
4.2 Related work 114
4.3 Depth-k skyline query 115
4.3.1 Loop-checking algorithm 116
4.3.2 Sorted-loop-checking algorithm 117
4.4 Accelerating depth-k skyline query processing in distribute systems by sifting 119
4.4.1 Real-value sifter (RVS) 120
4.4.2 Neural-based sifter (NS) 121
4.4.2.1 The structure of neural-based sifter 122
4.4.2.2 Algorithm of the neural-based sifter 123
4.5 Simulations 125
4.5.1 Comparisons of the loop-checking algorithm and the sorted-loop-checking algorithm 127
4.5.2 Comparisons of RVS and NS 128
4.5.3 Using NS in distributed system 130
4.6 Summary 132
Chapter 5 G-tree: A Novel Index Structure for Subspace Skyline Query 133
5.1 Introduction 133
5.2 G-tree 137
5.2.1 G-tree structure 137
5.2.2 G-tree construction 139
5.3 Using G-tree to find the subspace skyline points 140
5.4 Performance 143
5.5 Summary 144
Chapter 6 The Skyline Path Query with Aggregate Attributes 146
6.1 Introduction 146
6.2 Related Work 154
6.2.1 Identifying Skyline Landmarks in Road Networks 154
6.2.2 Identifying Skyline Paths in Road Networks 155
6.3 Definitions 156
6.4 Finding Skyline Paths from the Road Network with Aggregate Attributes 158
6.4.1 One hop tree 158
6.4.1.1 Parameters in a leaf node 160
6.4.1.2 Parameters in an internal node 163
6.4.1.3 Tree formulation 166
6.4.2 SPA algorithm 169
6.4.2.1 Initialization phase 170
6.4.2.2 Examination phase 175
6.5 Simulations 182
6.5.1 Influence of Aggregate Attributes and Edge Attributes on Skyline Paths 183
6.5.2 Efficiency of SPA Algorithm with One-Hop Tree 186
6.6 Summary 192
Chapter 7 Conclusions 193
References 196
Appendix A The pseudo code of the Rσ-N algorithm 202
Appendix B The overlapping area between two M+BRs in an M+-tree 204
Appendix C The pseudo code of the Mσ-N algorithm 208

[1] K. Altun and B. Barshan, “Human activity recognition using inertial/magnetic sensor units, Lecture Notes in Computer Science, vol. 6219, pp. 38-51, 2010.
[2] M. Bai, J. Xin, and G. Wang, “Subspace global skyline query processing, Proceeding on EDBT, 2013.
[3] W. Balke, U. Guentzer, and J. X. Zheng, “Efficient Distributed Skylining for Web Information Systems, Proceeding on EDBT, pp. 256-273, 2004.
[4] I. Bartolini, P. Ciaccia, and M. Patella, “SaLSa: Computing the skyline without scanning the whole sky, Proceeding on CIKM, pp. 405-414, 2006.
[5] I. Bartolini, P. Ciaccia, and M. Patella, “Efficient sort-based skyline evaluation, ACM Transactions on Database Systems, vol. 33, no. 4, pp.31-48, 2008.
[6] N. Beckmann, H. P. Kriegel, R. Schneider, and B. Seeger, “The R*-tree: an efficient and robust access method for points and rectangles, Proceeding on SIGMOD, 1990.
[7] S. Borzsonyi, D. Kossmann, and K. Stocker, “The skyline operator,Proceeding on ICDE, pp. 235-254, 2001.
[8] L. Chen, B. Cui, and H. Lu, “Constrained Skyline Query Processing against Distributed Data Sites, IEEE Trans. on Knowledge and Data Engineering, vol. 23, no. 2, pp. 204-217, 2011.
[9] Y. C. Chen, H. C. Liao, and C. Lee, “A Novel G-tree for Accelerating the Time-consuming Skyline Query,Proceeding on IKE, 2013.
[10] Z. Chen, H. T. Shen, X. Zhou, and J. X. Yu, “Monitoring path nearest neighbor in road networks, proceeding on SIGMOD, pp. 591-602, 2009.
[11] K. Choi, K. A. Toh, and H. Byun, “Realtime training on mobile devices for face recognition applications, Pattern Recognition, vol. 44, no. 2, pp. 386-400, 2011.
[12] J. Chomicki, P. Godfrey, J. Gryz, and D. Liang, “Skyline with presorting, Proceeding on ICDE, pp. 717-719, 2003.
[13] I. Chrysakis, C. Chalkidis, and D. Plexousakis, “Evaluation of Top-k queries in Peer-to-Peer Networks using Threshold Algorithms, Proceedings in CIKM, pp 1305-1308, 2010.
[14] P. Ciaccia, M. Patella, and P. Zezula, “M-tree: An efficient access method for similarity search in metric spaces, Proceeding on Int. Conf. on Vary large Data Bases (VLDB), pp.426-435, 1997.
[15] G. Cybenko, “Approximation by superpositions of a sigmoidal function, Mathematics of Control, Signals, and Systems, vol. 2, pp. 303-314, 1989.
[16] E. Dellis, A. Vlachou, I. Vladimirskiy, B. Seeger, and Y. Theodoridis, “Constrained subspace skyline computation, Proceeding on ACM Conf. on Information and Knowledge Management (CIKM), pp. 415-424, 2006.
[17] K. Deng, Y. Zhou, and H. Shen, “Multi-source query processing in road networks, proceeding on ICDE, pp. 796-805, 2007.
[18] P. K. Eng, B. C. Ooi, and K. L. Tan, “Indexing for progressive skyline computation, Data ＆ Knowledge Engineering, vol. 46, pp. 169-201, 2003.
[19] Y. Gao, J. Hu, G. Chen, and C. Chen, “Finding the most desirable skyline objects, Proceeding on Database System for Advanced Applications (DASFAA), 2010.
[20] P. Gil, A. Cardoso, and L. Palma, “Estimating the number of hidden neurons in recurrent neural networks for nonlinear system identification, Proceeding on IEEE International Symposium on Industrial Electronics, pp. 2053-2058, 2009.
[21] A. Guttman, “R-trees: A dynamic index structure for spatial searching, SIGMOD Record, vol. 14, no. 2, pp. 47-57, 1984.
[22] M. T. Hagan, H. B. Demuth, and M. Beale, Neural network design, Boston: PWS, 1997.
[23] Y. L. Hsu and J. S. Wang, “A Wiener-Type recurrent neural network and its control strategy for nonlinear dynamic applications, Journal of Process Control, vol. 19, no. 6, pp. 942-953, 2009.
[24] Y. L. Hsueh, R. Zimmermann, and W. S. Ku, “Caching support for skyline query processing with partially-ordered domains, proceeding on SIGSPATIAL, pp. 386-389, 2012.
[25] Y. K. Huang, C. H. Chang, and C. Lee, “Continuous distance-based skyline queries in road networks, Information Systems, vol. 37, no. 7, pp. 611-633, 2012.
[26] X. Huang and C. Jensen, “In-route skyline querying for location-based services, proceeding on W2GIS, pp. 120-135, 2004.
[27] W. Jin, A. K. H. Tung, M. Ester, and J. Han, “On Efficient Processing of Subspace Skyline Queries on High Dimensional Data, Proceeding on SSDBM, 2007.
[28] H. Jung, H. Han, H. Y. Yeom, and S. Kang, “A fast and progressive algorithm for skyline queries with totally- and partially-ordered domains, Journal of Systems and Software, vol. 83, no. 3, pp. 429-445, 2010.
[29] T. Kavzoglu, “Increasing the accuracy of neural network classification using refined training data, Environmental Modelling and Software, vol. 24, no. 7, pp. 850-858, 2009.
[30] J. Kim, J. Lee, and S. W. Hwang, “Skyline view: Efficient distributed subspace skyline computation, Proceeding on DaWaK, 2009.
[31] D. Kossmann, F. Ramsak, and S. Rost, “Shooting stars in the sky: an online algorithm for skyline queries, Proceeding on VLDB, 2002.
[32] H. P. Kriegel, M. Renz, and M. Schubert, “Route skyline queries: a multi-preference path planning approach, proceeding on ICDE, pp. 261-272, 2010.
[33] F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, abd S. Teng, “On trip planning queries in spatial databases, proceeding on SSTD, pp. 273-290, 2005.
[34] G. Li, and J. Tang, “A new R-tree spatial index based on space grid coordinate division, Proceeding on ICCE, 2011.
[35] S. Li, D. Zhao, and K. Bai, “A new approach of R-tree construction, Proceeding on ICCIS, pp. 684-687, 2012.
[36] X. Lin, Y. Yuan, Q. Zhang, Y. Zhang, “Selecting stars: The k most representative skyline operator, Proceeding on Int. Conf. on Data Engineering (ICDE), pp. 86-95, 2007.
[37] H. Lu, Y. Zhou, and J. Haustad, “Continuous skyline monitoring over distributed data streams, Lecture Notes in Computer Science, vol. 6187, pp. 565-583, 2010.
[38] H. Lu, C. S. Jensen, and Z. Zhang, “Flexible and Efficient Resolution of Skyline Query Size Constraints, IEEE Trans. on Knowledge and Data Engineering, vol. 23, no. 7, pp. 991-1005, 2011.
[39] D. Papadias, Y. Tao, G. Fu, and B. Seeger, “An optimal and progressive algorithm for skyline queries, Proceeding on SIGMOD, 2003.
[40] D. Papadias, Y. Tao, G. Fu, and B. Seeger, “Progressive skyline computation in database systems, ACM Trans. on database systems, vol. 30, no. 1, pp. 41-82, 2005.
[41] J. Pei, Y. Yuan, X. Lin, W. Jin, M. Ester, Q. Liu, W. Wang, Y. Tao, J. X. Yu, and Q. Zhang, “Towards multidimensional subspace skyline analysis, ACM Transactions on Database Systems, vol. 31, no. 4, pp. 1335-1381, 2006.
[42] V. Ramanathan and H. Wechsler, “Robust human authentication using appearance and holistic anthropometric features, Pattern Recognition Letters, vol. 31, no. 15, pp. 2425-2435, 2010.
[43] K. L. Tan, P. K. Eng, and B. C. Ooi, “Efficient progressive skyline computation, Proceeding on VLDB, pp. 301-310, 2001.
[44] Y. Tao, X. Xiao, and J. Pei, “SUBSKY: Efficient computation of skylines in subspaces, Proceeding on ICDE, pp. 65-74, 2006.
[45] Y. Tao, L. Ding, X. Lin and J. Pei, “Distance-based representative skyline, Proceeding on Int. Conf. on Data Engineering (ICDE), pp. 892-903, 2009.
[46] Y. Tian, K. C. K. Lee, and W. C. Lee, “Finding skyline paths in road networks, proceeding on ACM GIS, pp. 444-447, 2009.
[47] G. Valkanas and A. N. Papadopoulos, “Efficient and adaptive distributed skyline computation, Proceeding on SSDBM, 2010.
[48] A. Vlachou, C. Doulkeridis, Y. Kotidis, and M. Vazirgiannis, “SKYPEER: Efficient subspace skyline computation over distributed data, Proceeding on ICDE, 416-425, 2007.
[49] J. S. Wang and Y. C. Chen, “A Hammerstein-Wiener recurrent neural network with universal approximation capability, Proceedings in IEEE International Conference on Systems, Man and Cybernetics, pp. 1832-1837, 2008.
[50] J. Y. F. Yam and T. W. S. Chow, “A weight initialization method for improving training speed in feedforward neural network, Neurocomputing, vol. 30, no. 1-4, pp. 219-232, 2000.
[51] M. L. Yiu, E. Lo, and D. Yung, “Measuring the sky: On computing data cubes via skylining the measures, IEEE Trans. Knowledge and Data Engineering, vol. 24, no. 3, pp. 492-503, 2012.
[52] http://www.bing.com/maps/
[53] https://maps.google.com/
[54] http://www.mapquest.com/
[55] https://maps.yahoo.com/