(3.92.96.236) 您好!臺灣時間:2021/05/07 01:31
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:黃仁偉
研究生(外文):Jen-Wei Huang
論文名稱:一個有效率的資料庫間多物件搬移指令
論文名稱(外文):An Operation to Efficiently Migrate Spatial Objects between Two Spatial Databases
指導教授:陳靖國陳靖國引用關係
指導教授(外文):Jeang-Kuo Chen
學位類別:碩士
校院名稱:朝陽科技大學
系所名稱:資訊管理系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:129
中文關鍵詞:空間連結多物件存取R-tree空間搬移
外文關鍵詞:R-treeMultiple objects accessSpatial-joinSpatial-migrate
相關次數:
  • 被引用被引用:1
  • 點閱點閱:170
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:15
  • 收藏至我的研究室書目清單書目收藏:0
近年來空間資料庫已經被廣泛地使用在許多領域上,而R-tree是一個有效率的空間物件索引結構,最常用在二維空間物件的存取。以往有若干研究探討R-tree單一物件的存取操作,若一次只進行一個物件的搬移,則可能會導致兩棵R-trees的節點分別發生overflow或underflow的情況。使得兩棵R-trees的索引必須一再的重新建構,降低資料庫系統的效率。在本論文中,我們針對R-tree提出一個存取指令稱為空間搬移(spatial-migrate)指令。這個指令的功能是將二群分屬不同資料庫的物件進行多個物件合併的動作,亦即將一個資料庫中多個物件一次同時併入到另一個資料庫中,並調整資料庫相對應之R-tree。從多次單一物件的存取,改成一次多個物件存取,可以避免許多不必要的節點分裂或MBR調節,節省許多時間。在物件搬移的過程中,合併方的某些節點會因新增多個物件而導致多次overflow情況發生,我們的解決方法是將每一個這種節點分裂成若干個節點,也就是一次計算、產生足夠的節點來容納所有併入某個節點的物件,讓每一個節點最多只發生一次的節點分裂或MBR調整。另外,被合併方的節點因為在大量物件刪除的情況下可能會產生多個underflow的節點,傳統R-tree的處理方式是將這些節點刪除,並將每個被刪除節點包含的物件或子節點一個個重新插入R-tree中,如此反覆的插入物件將造成R-tree結構不斷重整,使得系統效率嚴重受到影響。因此,我們的作法是使用合併物件的方式,將刪除物件後所有剩餘的物件重新進行分配,然後由下而上重新建構R-tree,取代傳統重新插入物件的方式,避免R-tree在刪除物件後高度變小,但因重新插入物件又使得高度增加的情況一再發生。我們所提出的空間搬移指令可大幅減少在多物件存取時發生節點分裂和MBR調整,改善索引結構提升資料庫的績效。
In recent year, spatial databases have been increasingly and widely used in many applications. The R-tree supports a dynamic index structure for efficiently retrieving objects. In the past, several papers discussed the access of individual object in R-tree. If objects are migrated one by one, some nodes in the two R-trees may overflow or underflow repeatedly. The database performance may decrease because the two R-trees may be reconstructed again and again. In this thesis, we propose a new operation, call spatial-migrate, for R-tree. The function of this operation is to combine one group of objects into another group of objects according to a special relationship between the two groups of objects. That is, more than one spatial objects in one R-tree are migrated to another R-tree at the same time. When many single-object insertions/deletions are replaced by a multiple-objects insertion/deletion, many redundant node-splits and/or MBR-adjustments can be omitted. While processing spatial-migrate, some nodes overflow due to the insertion of many objects in the combining R-tree. Our method splits each of these nodes into several nodes. In other words, we once generate enough nodes to contain all the objects inserted into the old node. Each node at most has only one node-split and/or MBR-adjustment. Moreover, some nodes underflow due to the deletion of many objects in the combined R-tree. In tradition, the underflow nodes are deleted form R-tree and all objects or child node of these nodes must be reinserted into the combined R-tree. The R-tree is reconstructed again and again. The system performance will be influenced obviously. Hence, we use a mergence method to deal with the objects in underflow nodes. All remaining objects are redistributed to leaf nodes. Then the combined R-tree is reconstructed form bottom to top. Our method avoids the R-tree shorten after some objects are deleted from the R-tree but recover again after some objects are reinserted into the R-tree. Therefore, the proposed spatial-migrate operation can obviously reduce node-split and MBR-adjustment to efficiently improve index structure and database performance.
論文摘要 I
Abstract III
誌謝 V
目錄 VI
表目錄 X
圖目錄 XIII
第一章、緒論 1
1.1 研究背景和動機 1
1.2 研究目的與論文架構 3
第二章、文獻探討 5
2.1 R-tree家族 5
2.1.1 R-tree 5
2.1.2 Packed R-tree 7
2.1.3 R+-tree 7
2.1.4 R*-tree 9
2.1.5 X-tree (eXtended node tree) 9
2.2 R-tree家族的資料存取方式 12
2.2.1 搜尋操作 12
2.2.2 空間連結操作 12
2.2.3 新增操作 13
2.2.4 刪除操作 15
第三章、研究架構與方法 16
3.1 空間搬移功能說明 16
3.2 空間搬移的第一階段:連結物件 21
3.3 空間搬移的第二階段:複製物件 30
3.3.1 多物件新增概述 30
3.3.2 多物件新增演算法 32
3.3.3 實例說明 42
3.4 空間搬移的第三階段:刪除物件 46
3.4.1 多物件刪除概述 46
3.4.2 多物件刪除演算法 49
3.4.3 實例說明 52
第四章、實驗與分析 54
4.1 實驗環境 54
4.2 實驗測試資料 58
4.2.1 控制參數 58
(1) 節點最大分支度(M) 58
(2) 物件個數(N) 58
(3) 資料分配型態(D) 59
(4) 資料空間重疊比率(P) 59
4.3 實驗評估項目 66
4.4 實驗結果分析 66
4.4.1 均勻分配的多物件搬移操作 67
(1) 多物件新增操作 67
(2) 多物件刪除操作 73
(3) 空間搬移操作之總時間 79
4.4.2 常態分配的多物件搬移操作 87
(1) 多物件新增操作 87
(2) 多物件刪除操作 93
(3) 空間搬移操作之總時間 99
4.4.3 歪斜分配的多物件搬移操作 106
(1) 多物件新增操作 106
(2) 多物件刪除操作 111
(3) 空間搬移操作之總時間 116
第五章、結論與未來工作 123
表目錄
表1、空間搬移操作的資料結構說明 20
表2、三種節點容量之比較 48
表3、實驗控制參數值列表 66
表4、空間重疊率25%的多重物件新增操作的平均反應時間 69
表5、空間重疊率50%的多重物件新增操作的平均反應時間 70
表6、空間重疊率75%的多重物件新增操作的平均反應時間 71
表7、空間重疊率100%的多重物件新增操作的平均反應時間 72
表8、空間重疊率25%的多重物件刪除操作的平均反應時間 75
表9、空間重疊率50%的多重物件刪除操作的平均反應時間 76
表10、空間重疊率75%的多重物件刪除操作的平均反應時間 77
表11、空間重疊率100%的多重物件刪除操作的平均反應時間 78
表12、空間重疊率25%的多重物件的空間搬移平均反應時間 82
表13、空間重疊率50%的多重物件的空間搬移平均反應時間 83
表14、空間重疊率75%的多重物件的空間搬移平均反應時間 84
表15、空間重疊率100%的多重物件的空間搬移平均反應時間 85
表16、空間重疊率25%的物件資料進行新增操作的平均反應時間 89
表17、空間重疊率50%的物件資料進行新增操作的平均反應時間 90
表18、空間重疊率75%的物件資料進行新增操作的平均反應時間 91
表19、空間重疊率100%的物件資料進行新增操作的平均反應時間 92
表20、空間重疊率25%的物件資料進行刪除操作的平均反應時間 95
表21、空間重疊率50%的物件資料進行刪除操作的平均反應時間 96
表22、空間重疊率75%的物件資料進行刪除操作的平均反應時間 97
表23、空間重疊率100%的物件資料進行刪除操作的平均反應時間 98
表24、空間重疊率25%的多重物件的空間搬移平均反應時間 101
表25、空間重疊率50%的多重物件的空間搬移平均反應時間 102
表26、空間重疊率75%的多重物件的空間搬移平均反應時間 103
表27、空間重疊率100%的多重物件的空間搬移平均反應時間 104
表28、空間重疊率25%的物件資料進行新增操作的平均反應時間 107
表29、空間重疊率50%的物件資料進行新增操作的平均反應時間 108
表30、空間重疊率75%的物件資料進行新增操作的平均反應時間 109
表31、空間重疊率100%的物件資料進行新增操作的平均反應時間 110
表32、空間重疊率25%的物件資料進行刪除操作的平均反應時間 112
表33、空間重疊率50%的物件資料進行刪除操作的平均反應時間 113
表34、空間重疊率75%的物件資料進行刪除操作的平均反應時間 114
表35、空間重疊率100%的物件資料進行刪除操作的平均反應時間 115
表36、空間重疊率25%的多重物件的空間搬移平均反應時間 118
表37、空間重疊率50%的多重物件的空間搬移平均反應時間 119
表38、空間重疊率75%的多重物件的空間搬移平均反應時間 120
表39、空間重疊率100%的多重物件的空間搬移平均反應時間 121
圖目錄
圖1、R-tree的範例 7
圖2、R+-tree的物件分佈及其結構圖(取自文獻[24]) 8
圖3、不同維度下R-tree資料搜尋的時間(取自文獻[4]) 11
圖4、不同維度下R*-tree非葉節點的重疊情況(取自文獻[4]) 11
圖5、X-tree結構圖(取自文獻[4]) 11
圖6、遞迴式的節點分割(取自文獻[24]) 15
圖7(a)、第一群的空間物件分佈 17
圖7(b)、R-tree R的索引結構 17
圖8(a)、第二群的空間物件分佈 18
圖8(b)、R-tree S的索引結構 18
圖9、兩群空間物件重疊的情況 19
圖10(a)、OPN 的資料結構 21
圖10(b)、DOT中存放兩個OPN記錄 21

圖11、逐層檢查分屬於R和S的節點或物件是否有重疊 22
圖12(a)、Branch的資料結構 23
圖12(b)、NPT中存放兩個Branch記錄 23
圖13(a)、執行空間連結後Level 1的DOT與NPT結果 25
圖13(b)、執行空間連結後Level 2的DOT與NPT結果 25
圖13(c)、執行空間連結後Level 3的DOT與NPT結果 26
圖14、刪除多餘的記錄後的DOT內容 27
圖15、刪除不必要的記錄後的DOT內容 28
圖16(a)、CPI的資料結構 33
圖16(b)、CPA中兩個CPI記錄 33
圖17、多物件同時新增時R-tree狀況及CPA內容 35
圖18、葉節點分裂後之R-tree狀況與CPA內容 36
圖19、從DOT取出有相同parentR欄位值的記錄儲存於CPA 44
圖20、將物件s4和s5併入節點R7的過程 44
圖21、將物件s10, s11, s12和s9併入節點R6的過程 45
圖22、R-tree R完成多物件插入後最終的物件分佈及結構圖 45
圖23、R-tree S中的若干物件要被刪除 53
圖24、R-tree S最後結果 53
圖25、合併方物件均勻分配之分佈情況 55
圖26、被合併方物件均勻分配之分佈情況 55
圖27、合併方物件常態分配之分佈情況 56
圖28、被合併方物件常態分配之分佈情況 56
圖29、合併方物件歪斜分配之分佈情況 57
圖30、被合併方物件歪斜分配之分佈情況 57
圖31、均勻分配的兩個資料空間有25%重疊 60
圖32、均勻分配的兩個資料空間有50%重疊 60
圖33、均勻分配的兩個資料空間有75%重疊 61
圖34、均勻分配的兩個資料空間有100%重疊 61
圖35、常態分配的兩個資料空間有25%重疊 62
圖36、常態分配的兩個資料空間有50%重疊 62
圖37、常態分配的兩個資料空間有75%重疊 63
圖38、常態分配的兩個資料空間有100%重疊 63
圖39、歪斜分配的兩個資料空間有25%重疊 64
圖40、歪斜分配的兩個資料空間有50%重疊 64
圖41、歪斜分配的兩個資料空間有75%重疊 65
圖42、歪斜分配的兩個資料空間有100%重疊 65
圖43、空間重疊率25%的多重物件新增操作的平均反應時間曲線 69
圖44、空間重疊率50%的多重物件新增操作的平均反應時間曲線 70
圖45、空間重疊率75%的多重物件新增操作的平均反應時間曲線 71
圖46、空間重疊率100%的多重物件新增操作的平均反應時間曲線 72
圖47、空間重疊率25%的多重物件刪除操作的平均反應時間曲線 75
圖48、空間重疊率50%的多重物件刪除操作的平均反應時間曲線 76
圖49、空間重疊率75%的多重物件刪除操作的平均反應時間曲線 77
圖50、空間重疊率100%的多重物件刪除操作的平均反應時間曲線 78
圖51、空間重疊率25%的多重物件搬移操作的平均反應時間曲線 82
圖52、空間重疊率50%的多重物件搬移操作的平均反應時間曲線 83
圖53、空間重疊率75%的多重物件搬移操作的平均反應時間曲線 84
圖54、空間重疊率100%的多重物件搬移操作的平均反應時間曲線 85
圖55、在均勻分配條件下兩個空間搬移操作時間曲線圖 86
圖56、空間重疊率25%的多重物件新增操作的平均反應時間曲線 89
圖57、空間重疊率50%的多重物件新增操作的平均反應時間曲線 90
圖58、空間重疊率75%的多重物件新增操作的平均反應時間曲線 91
圖59、空間重疊率100%的多重物件新增操作的平均反應時間曲線 92
圖60、空間重疊率25%的多重物件刪除操作的平均反應時間曲線 95
圖61、空間重疊率50%的多重物件刪除操作的平均反應時間曲線 96
圖62、空間重疊率75%的多重物件刪除操作的平均反應時間曲線 97
圖63、空間重疊率100%的多重物件刪除操作的平均反應時間曲線 98
圖64、空間重疊率25%的多重物件搬移操作的平均反應時間曲線 101
圖65、空間重疊率50%的多重物件搬移操作的平均反應時間曲線 102
圖66、空間重疊率75%的多重物件搬移操作的平均反應時間曲線 103
圖67、空間重疊率100%的多重物件搬移操作的平均反應時間曲線 104
圖68、在常態分配條件下兩個空間搬移操作時間曲線圖 105
圖69、空間重疊率25%的多重物件新增操作的平均反應時間曲線 107
圖70、空間重疊率50%的多重物件新增操作的平均反應時間曲線 108
圖71、空間重疊率75%的多重物件新增操作的平均反應時間曲線 109
圖72、空間重疊率100%的多重物件新增操作的平均反應時間曲線 110
圖73、空間重疊率25%的多重物件刪除操作的平均反應時間曲線 112
圖74、空間重疊率50%的多重物件刪除操作的平均反應時間曲線 113
圖75、空間重疊率75%的多重物件刪除操作的平均反應時間曲線 114
圖76、空間重疊率100%的多重物件刪除操作的平均反應時間曲線 115
圖77、空間重疊率25%的多重物件搬移操作的平均反應時間曲線 118
圖78、空間重疊率50%的多重物件搬移操作的平均反應時間曲線 119
圖79、空間重疊率75%的多重物件搬移操作的平均反應時間曲線 120
圖80、空間重疊率100%的多重物件搬移操作的平均反應時間曲線 121
圖81、在歪斜分配條件下兩個空間搬移操作時間曲線圖 122
[1] 陳靖國、黃仁偉(2007),「R-tree一個多物件刪除的指令」,第一屆資訊科技國際研討會,朝陽科技大學。
[2] Jochen van den Bercken, B. Seeger, and P. Widmayer(1997), “A Generic Approach to Bulk Loading Multidimensional Index Structures”, in Proceedings of the 23rd VLDB Conference, Athens, Greece, pp. 406-415.
[3]N. Beckmann, H. P. Kriegel, R. Schneider, B. Seeger(1990), “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles”, in Proceedings of ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, pp. 322-331.
[4]S. Berchtold, D. A. Keim, and H. P. Kriegel(1996), “The X-tree: An Index Structure for High-Dimensional Data”, in Proceedings of 22th Internal Conference on VLDB, Mumbai(Bombay), India, pp. 28-39.
[5]T. Brinkhoff, H. P. Kriegel and B. Seeger(1993), “Efficient Processing of Spatial Joins Using R-trees”, in Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 237-246.
[6]J. K. Chen(2005), “Concurrency Control of Spatial Join on Spatial Database”, in Proceedings of the Fourth Annual ACIS International Conference on Computer and Information Science, Vol.00, pp.693-697.
[7]V. Gaede and O. Gunther(1997), “Multidimensional Access Methods”, ACM Computing Surveys, pp. 170–231.
[8]A. Guttman(1984), “R-trees: A Dynamic Index Structure for Spatial Searching”, in Proceedings of the ACM SIGMOD, pp. 47-57.
[9]Y. W. Hung, N. Jing, and E. A. Rundesteiner(1997), “Spatial Joins Using R-trees:Breadth-First Traversal with Global Optimizations”, in Proceedings of the 23rd VLDB Conference, Athens, Greece, pp. 396-405.
[10]Y. W. Hung, N. Jing, and E.A. Rundesteiner(1997), “BFRJ:Global Optimization of Spatial Joins Using R-trees”, Technical Report, WPI-CS-TR-97-5, Dept. of Computer Science, Worcester Polytechnic Institute, January.
[11]P. W. Huang, P. L. Lin, and H. Y. Lin(2001), “Optimizing Storage Utilization in R-tree Dynamic Index Structure for Spatial Databases”, Journal of Systems and Software of Elsevier Science, Vol. 55, No. 3, pp. 291-299.
[12]R. Jain(1991), “The Art of Computer Systems Performance Analysis”, Wiley, New York.
[13]T. Johnson, and D. Sasha(1993), “The Performance of Current B-tree Algorithms”, ACM Transactions on Database System, Vol. 18, No. 1, pp. 51-101.
[14]A. Kumar(1994), “G-tree: A New Data Structure for Organizing Multidimensional Data”, IEEE Trans. Knowl. Data Eng., Vol. 6, No. 2, pp. 341–347.
[15] T. Lee, B. Moon, and S. Lee(2006), “Bulk Insertion for R-trees by Seeded Clustering” Data & Knowledge Engineering, Vol. 59, Issue. 1, pp. 86-106.
[16]M. Mihail, Y. Theodoridis, H. Frentozs, R-tree Portal, 2006, http://www.rtreeportal.org/index.php?option=com_content&task=view&id=28&Itemid=41.
[17]J. K. Chen and J. W. Huang, “Multiple Spatial Objects Insertion in R-trees,” Proceedings of the 12th International Conference on Distributed Multimedia Systems, Sep. 2006.
[18]J. K. Chen and J. W. Huang, “A New Operation for Two R-trees to Efficiently Migrate Spatial Objects,” Proceedings of International Computer Symposium, December 2006.
[19]J. Nievergelt, H. Hinterberger, and K. C. Sevcik(1984), “The Grid File: An Adaptable, Symmetric Multikey File Structure”, ACM Transactions on Database System, Vol. 9, No. 1, pp. 38–71.
[20]J. M. Patel and D. J. DeWitt(1996), “Partition Based Spatial-Merge Join”, in Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 259-270.
[21]J. T. Robinson(1981), “The K-D-B-tree: A Search Structure for Large Multidimensional Dynamic Indexes”, in Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 10–18.
[22]N. Roussopoulos and D. Leifker(1985), “Direct Spatial Search on Pictorial Databases Using Packed R-trees”, in Proceedings of the ACM SIGMOD, pp. 17-31.
[23]N. Roussopoulos, S. Kelly, and F. Vincent(1995), “Nearest Neighbor Queries”, in Proceedings of ACM SIGMOD International Conference on Management of Data, San Jose, California, pp. 71-79.
[24]T. Sellis, N. Roussopoulos, C. Faloutsos(1987), “The R+-Tree: A Dynamic Index for Multi-Dimensional Objects”, in Proceedings of the13th VLDB conference, Brighton, pp.507-518.
[25]K. Sevcik and D. N. Koudas(1996), “Filter Trees for Managing Spatial Data Over a Range of Size Granularities”, in Proceedings of the 22th VLDB Confenence, Bombay, pp. 16-27.
[26] L. Stanescu, D. D. Burdescu, and C. S. Spahiu(2005), “Using R-Trees in Content-Based Region Query with Spatial Bounds”, SYNASC, IEEE Computer Society, pp. 83-89.
[27] C. H. Wu, L. P. Chang, and T. W. Kuo(2003), “An Efficient R-tree Implementation Over Flash-Memory Storage Systems”, in Proceedings of the 11th ACM international symposium on Advances in GIS, pp. 17-24.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔