成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	陳奕中 Chen, Yi-Chung
論文名稱：	改善天際線搜尋效率及可用性之研究 A Study on Enhancing the Efficiency and Applicability of Skyline Queries
指導教授：	李強 Lee, Chiang
學位類別：	博士 Doctor
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2014
畢業學年度：	102
語文別：	英文
論文頁數：	209
中文關鍵詞：	資料庫、天際線查詢、類神經網路、索引樹架構、道路網路
外文關鍵詞：	Database, Skyline query, Neural network, Index tree structure, Road network
相關次數：	點閱：189 下載：5
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

近來有越來越多的學者們著手於多條件查詢處理技術之研究。我們的研究主要使用了天際線查詢來找出多條件查詢的結果。給予一個具有多個維度的資料庫，這個查詢可以回傳所有不被「支配」（細節將於本論文中介紹）的資料點。本論文分為兩個部分。第一個部分介紹了三個過往執行天際線查詢或其應用時會遇到的困難。這些困難包含了資料庫中過多的資料量會嚴重影響天際線搜尋的執行效率、天際線搜尋無法針對資料庫中無法量化的維度進行查詢，以及執行子維度天際線搜尋時的低效率問題。第二個部分討論了如何將天際線搜尋應用至其他環境上，包含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  Motivation	1
2  Overview of the Dissertation	4
2.1  Neural Skyline Filter for Accelerating Skyline Search Algorithms	4
2.2  The σ-Neighborhood Skyline Queries	5
2.3  Depth-k skyline query for unquantifiable attributes in distributed systems	5
2.4  G-tree: A Novel Index Structure for Subspace Skyline Query	6
2.5  The Skyline Path Query with Aggregate Attributes	6
3  Organization of the Dissertation	7
Chapter 2  Neural Skyline Filter for Accelerating Skyline Search Algorithms	8
1  Introduction	8
2  Related work	12
2.1  Block nested loop (BNL)	12
2.2  Divide-and-conquer (DAC)	13
2.3  Sort filter skyline (SFS)	14
2.4  Branch-and-bound skyline (BBS)	15
2.5  Neural Networks	17
3  Naïve skyline filter	19
3.1  Filtering Point Sieving Phase	20
3.2  Filtering Phase	20
3.3  Efficiency of the Naïve Skyline Filter	22
4  Neural skyline filter (NuSF)	23
4.1  Structure of the Neural Skyline Filter	24
4.2  Neural Skyline Filter Construction Algorithm	27
4.2.1  Training Data Generation Phase	28
4.2.2  Neural Skyline Filter Initialization Phase	31
4.2.3  Neural Skyline Filter Training Phase	33
4.3  Neural Skyline Filter Query Processing Mechanism	35
4.4  Universal Approximation of the Neural Skyline Filter	36
4.5  Brief Summary	38
5  Featured neural skyline filter (FNuSF) 	38
5.1  Structure of the Featured Neural Skyline Filter	40
5.2  Construction Algorithm for Featured Neural Skyline Filter	42
5.3  Mechanism of Featured Neural Skyline Filter for Processing Queries	42
5.4  Brief Summary	43
6  Completeness of the skyline points	43
7  Performance evaluation	46
7.1  Comparisons of the SNF, the NuSF, and the FNuSF	47
7.2  Completeness of the Skyline Points	55
7.3  Using FNuSF as a Filter for Skyline Search	57
7.3.1  Proper Number of Hidden Neurons in FNuSF	57
7.3.2  Performance of Skyline Search Using the FNuSF	58
7.3.3  Time cost of operating the FNuSF	64
8  Summary	67
Chapter 3  The σ-Neighborhood Skyline Queries	68
1  Introduction	68
2  Problem Definition	72
3  An R-tree-based method for Σ-N skyline queries	74
3.1  Spatial relationships between an σ-N skyline region and an MBR or point of an R-tree	75
3.2  Rσ-N Algorithm	76
4  An M+-tree-based method for Σ-N skyline queries	83
4.1  M+-tree	84
4.2  The merits of using the M+-tree in σ-N skyline queries	87
4.3  The Mσ-N algorithm	89
4.3.1  Inheritance-based pruning mechanism	89
4.3.2  Summation-checking mechanisms	91
4.3.3  Inequality-based pruning mechanisms	96
4.3.4  An example	97
5  Simulation 	101
5.1  Finding a suitable σ for different datasets	102
5.2  Effect of dimensionality	105
5.3  Effect of Cardinality	107
5.4  Effect of σ	108
6  Summary	110
Chapter 4  Depth-k skyline query for unquantifiable attributes in distributed systems	111
1  Introduction	111
2  Related work	114
3  Depth-k skyline query	115
3.1  Loop-checking algorithm	116
3.2  Sorted-loop-checking algorithm	117
4  Accelerating depth-k skyline query processing in distribute systems by sifting	119
4.1  Real-value sifter (RVS)	120
4.2  Neural-based sifter (NS)	121
4.2.1  The structure of neural-based sifter	122
4.2.2  Algorithm of the neural-based sifter	123
5  Simulations 	125
5.1  Comparisons of the loop-checking algorithm and the sorted-loop-checking algorithm	127
5.2  Comparisons of RVS and NS	128
5.3  Using NS in distributed system	130
6  Summary	132
Chapter 5  G-tree: A Novel Index Structure for Subspace Skyline Query	133
1  Introduction	133
2  G-tree	137
2.1  G-tree structure	137
2.2  G-tree construction	139
3  Using G-tree to find the subspace skyline points	140
4  Performance	143
5  Summary	144
Chapter 6  The Skyline Path Query with Aggregate Attributes	146
1  Introduction	146
2  Related Work	154
2.1  Identifying Skyline Landmarks in Road Networks	154
2.2  Identifying Skyline Paths in Road Networks	155
3  Definitions	156
4  Finding Skyline Paths from the Road Network with Aggregate Attributes	158
4.1  One hop tree	158
4.1.1  Parameters in a leaf node	160
4.1.2  Parameters in an internal node	163
4.1.3  Tree formulation	166
4.2  SPA algorithm	169
4.2.1  Initialization phase	170
4.2.2  Examination phase	175
5  Simulations	182
5.1  Influence of Aggregate Attributes and Edge Attributes on Skyline Paths	183
5.2  Efficiency of SPA Algorithm with One-Hop Tree	186
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/

校內：2019-06-11公開
校外：2019-06-11公開

簡易檢索 / 詳目顯示

相關論文