淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0407200713360100
中文論文名稱 利用基因演算法之R-Tree之建置
英文論文名稱 R-Tree Construction Using Genetic Algorithms
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 95
學期 2
出版年 96
研究生中文姓名 陳柏欽
研究生英文姓名 Po-Chin Chen
學號 694521310
學位類別 碩士
語文別 中文
口試日期 2007-06-15
論文頁數 56頁
口試委員 指導教授-梁恩輝
委員-謝禎冏
委員-吳瑞堯
委員-周清江
中文關鍵字 R-Tree  基因演算法  STR  OMT 
英文關鍵字 R-Tree  Genetic Algorithms  STR  OMT 
學科別分類 學科別社會科學管理學
學科別社會科學資訊科學
中文摘要 R-Tree是一種被廣泛使用在空間及多維度資料庫的多維度資料索引技巧[14],由Guttman在1984年提出。優良的R-Tree可令查詢動作更有效率,且應具有「目錄矩形涵蓋區域面積較小」及「目錄矩形間重疊的區域面積較小」兩特性[17]。建置R-Tree的主要工作,在於為空間物件依其所在位置取得良好的分組。在過去的研究中,對於建置R-Tree只採用特定的演算法,難以應付真實空間物件在分佈上的多種可能性,以致時常建置出查詢效率不佳的R-Tree。因此,為能普遍因應各種空間資料之特性,本研究利用基因演算法( Genetic Algorithms )「尋求最佳解」的能力,建置R-Tree。本研究透過實驗與Sort-Tile-Recursive( STR ) Algorithm[14]及Overlap Minimizing Top-down( OMT ) Bulk Loading Algorithm[13]進行比較與分析,說明本研究所提出之演算法的成效。
英文摘要 R-tree is a common indexing technique for multi-dimensional data and is widely used in spatial and multi-dimensional databases[14]. It was proposed by Guttman in 1984. A quality R-Tree can make the query more efficient. It should satisfy two properties: “less overlap between the directory rectangles” and “less area of directory rectangles”[17]. The main work to construct an efficient R-Tree is to group the spatial objects well according to their position. In past research, R-Trees are usually implemented using specific algorithms. However, specific algorithms can not deal with various possibilities of distribution for spatial objects. Hence, inefficient R-Trees are usually implemented. In order to construct efficient R-Trees over all kinds of datasets, we make use of Genetic Algorithms which can search for optimal solution to construct R-Trees. Finally, we compared the R-Trees implemented by our methods with those implemented by Sort-Tile-Recursive( STR ) Algorithm[14] and Overlap Minimizing Top-down( OMT ) Bulk Loading Algorithm[13], and then analyzed the fruitage of our methods.
論文目次 目 錄
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機與目的 1
第二章 相關研究 2
2.1 R-Tree 2
2.2 R-Tree的點查詢 6
2.3 R-Tree的區域查詢 8
2.4 R-Tree的應用 10
2.5 基因演算法 10
2.5.1 何謂基因演算法 10
2.5.2 基因演算法的基本架構 11
2.5.3 基因演算法主要運算過程 12
2.6 STR Algorithm 14
2.7 OMT Bulk Loading Algorithm 15
第三章 以基因演算法建置R-Tree 17
3.1 初始族群( Initial Population ) 17
3.2 適應函式( Fitness Function ) 22
3.3 選擇函式( Selection Function ) 22
3.4 交配方式( Crossover ) 23
3.5 突變方式( Mutation ) 24
3.6 建置R-Tree 25
3.7 根據STR Algorithm結果之基因演算法 27
第四章 實驗與分析 28
4.1 測試資料 29
4.2 實驗結果 34
4.3 實驗結果數據 45
4.4 實驗分析 50
第五章 結論 54
參考文獻 55

圖 目 錄
圖 1. 最小邊界矩形 2
圖 2. 節點間的重疊區域 4
圖 3. R-Tree範例 6
圖 4. 點查詢範例 7
圖 5. 點查詢路徑 8
圖 6. 區域查詢範例 9
圖 7. 區域查詢路徑 10
圖 8. 初始族群 18
圖 9. Solution的解譯 19
圖 10. 適當的分群 20
圖 11. 不適當的分群 20
圖 12. matching section 23
圖 13. 突變範例1 25
圖 14. 突變範例2 25
圖 15. 建置R-Tree的流程圖 26
圖 16. 測試資料一( Long Island地區 ) 30
圖 17. 測試資料二( Chicago地區 ) 30
圖 18. 測試資料三( Detroit地區 ) 31
圖 19. 測試資料四( Sacramento地區 ) 31
圖 20. 測試資料五( Charlotte地區 ) 32
圖 21. 測試資料六( Brooklyn地區 ) 32
圖 22. 測試資料七( 虛擬資料 ) 33
圖 23. 測試資料一( GA )實驗結果 34
圖 24. 測試資料一( STR )實驗結果 35
圖 25. 測試資料一( GAonSTR )實驗結果 35
圖 26. 測試資料二( GA )實驗結果 36
圖 27. 測試資料二( STR )實驗結果 36
圖 28. 測試資料二( GAonSTR )實驗結果 37
圖 29. 測試資料三( GA )實驗結果 37
圖 30. 測試資料三( STR )實驗結果 38
圖 31. 測試資料三( GAonSTR )實驗結果 38
圖 32. 測試資料四( GA )實驗結果 39
圖 33. 測試資料四( STR )實驗結果 39
圖 34. 測試資料四( GAonSTR )實驗結果 40
圖 35. 測試資料五( GA )實驗結果 40
圖 36. 測試資料五( STR )實驗結果 41
圖 37. 測試資料五( GAonSTR )實驗結果 41
圖 38. 測試資料六( GA )實驗結果 42
圖 39. 測試資料六( STR )實驗結果 42
圖 40. 測試資料六( GAonSTR )實驗結果 43
圖 41. 測試資料七( GA )實驗結果 43
圖 42. 測試資料七( STR )實驗結果 44
圖 43. 測試資料七( GAonSTR )實驗結果 44
圖 44. 群組面積和變化示意圖 51


表目錄
表 1. 測試資料一實驗結果數據 45
表 2. 測試資料二實驗結果數據 46
表 3. 測試資料三實驗結果數據 46
表 4. 測試資料四實驗結果數據 47
表 5. 測試資料五實驗結果數據 47
表 6. 測試資料六實驗結果數據 48
表 7. 測試資料七實驗結果數據 48
表 8. 查詢的平均節點拜訪次數 49
參考文獻 [1] Beckman, N., H. P. Kriegel, “The R* tree: An efficient and robust access method for points and rectangles”, Proc. ACM SIGMOD, pp. 322-331, 1990.
[2] Bhuyan, J. N., V. V. Raghavan, V. K. Elayavalli, “Genetic algorithm for clustering with an ordered representation”, Belew and Booker, pp. 408-415, 1991.
[3] Chambers, L., “The Practical Handbook of Genetic Algorithms Applications”, CHAPMAN & HALL / CRC, 2001.
[4] Falkenauer, E., “Genetic Algorithms and Grouping Problems”, John Wiley & Sons, 1998.
[5] Gavrila, D. W., “R-Tree Index Optimization”, Tech. Report CS- TR-3292, Univ. of Maryland, College Park, June 1994.
[6] Goldberg, D. E., “Genetic Algorithms in Search, Optimization and Machine Learning”, Addison-Wesley, 1998.
[7] Guttman, A., “R-Tree : A Dynamic Index Structure for Spatial Searching”, Proc. ACM SIGMOD, pp.47-57, 1984.
[8] Haupt, R. L., “An introduction to genetic algorithms for electromagnetics”, IEEE Antennas, 1995.
[9] Holland, J. H., “Adaptation in Natural and Artificial System”, Ann Arbor: The University of Michigan Press, 1975.
[10] Jones, D. R., M. A. Beltramo, “Solving partitioning problems with genetic algorithms”, Belew and Booker, pp. 442-449, 1991.
[11] Koza, J. R., “Survey of Genetic Algorithms and Genetic Programming”, WESCON/'95. Conference, 1995.
[12] Kumar, A., R. M. Pathak, M. C. Gupta, “Genetic algorithm based approach for designing computer network topology”, Proc. ACM Computer science, 1993.
[13] Lee, T., S. Lee, “OMT – Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree”, Proceedings of Short Papers at 15th Conference on Advanced Information Systems Engineering (CAiSE’03), Klagenfurt, Austria, 2003.
[14] Leutengger, S. T., M. Lopez, J. Edgington, “STR: A Simple and Efficient Algorithm for R-Tree Packing”, Proc. of the 14th Int. Conf. on Data Engineering, pp.497-506, 1997.
[15] Manolopoulos, Y., A. Nanopoulos, A. N. Papadopoulos, Y. Theodoridis, “R-Trees: Theory and Applications”, Springer, 2006.
[16] Neumann, L., “The R-Tree”, Algorithms and Data Structures for Persistent Data, 2001.
[17] Popescu, A. R., “A Study of R-tree Based Spatial Access Methods”, University of Helsinki, 2003.
[18] Reeves, C., “Hybrid genetic algorithms for bin-packing and related problems”, Annals of Operations Research, 1993.
[19] Rigaux, P., M. Scholl, A. Voisard, “Spatial Databases with application to GIS”, Morgan Kaufmann, 2002.
[20] Smith, Derek, “Bin packing with adaptive search”, Grefenstette, pp. 202-207, 1985.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2012-07-05公開。
  • 同意授權瀏覽/列印電子全文服務,於2012-07-05起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信