(3.92.96.236) 您好！臺灣時間：2021/05/07 01:31

### 詳目顯示:::

:

• 被引用: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.
 論文摘要 IAbstract III誌謝 V目錄 VI表目錄 X圖目錄 XIII第一章、緒論 11.1 研究背景和動機 11.2 研究目的與論文架構 3第二章、文獻探討 52.1 R-tree家族 52.1.1 R-tree 52.1.2 Packed R-tree 72.1.3 R+-tree 72.1.4 R*-tree 92.1.5 X-tree (eXtended node tree) 92.2 R-tree家族的資料存取方式 122.2.1 搜尋操作 122.2.2 空間連結操作 122.2.3 新增操作 132.2.4 刪除操作 15第三章、研究架構與方法 163.1 空間搬移功能說明 163.2 空間搬移的第一階段：連結物件 213.3 空間搬移的第二階段：複製物件 303.3.1 多物件新增概述 303.3.2 多物件新增演算法 323.3.3 實例說明 423.4 空間搬移的第三階段：刪除物件 463.4.1 多物件刪除概述 463.4.2 多物件刪除演算法 493.4.3 實例說明 52第四章、實驗與分析 544.1 實驗環境 544.2 實驗測試資料 584.2.1 控制參數 58(1) 節點最大分支度(M) 58(2) 物件個數(N) 58(3) 資料分配型態(D) 59(4) 資料空間重疊比率(P) 594.3 實驗評估項目 664.4 實驗結果分析 664.4.1 均勻分配的多物件搬移操作 67(1) 多物件新增操作 67(2) 多物件刪除操作 73(3) 空間搬移操作之總時間 794.4.2 常態分配的多物件搬移操作 87(1) 多物件新增操作 87(2) 多物件刪除操作 93(3) 空間搬移操作之總時間 994.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.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 可供快速查詢的空間物件統計資料索引裝置

 無相關期刊

 1 運用多本分類式編碼簿之預測式邊緣吻合向量量化資訊隱藏法 2 以服務導向架構開發策略性人力資源管理資訊系統之研究 3 多重關鍵字搜尋在動態XML文件之研究 4 結合就醫態度與行為資料預測忠誠病患之研究 5 以磁字及印刷字元為基礎支票辨識之研究 6 消費者持續購買非營利組織網路義賣品意願之研究—以台灣地區為例 7 概念關係應用於學習迷思診斷系統之開發 8 運用具學習能力的領域知識本體於線上FAQ系統 9 以簡訊與雜湊實作一次性密碼機制之行動身分認證機制 10 植基於顯著影像特徵之強韌型浮水印技術 11 使用有效率的低階特徵選取於場景分類 12 數位相機自動曝光機制之研究 13 無線感測網路之金鑰預先分配機制研究 14 資訊系統版本更新之顧客滿意度研究 15 客戶服務中心員工生涯錨研究-以中華電信行動通信分公司台中營運處為例

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室