資源描述：
《R樹和四叉樹的空間索引結構“RQOP”樹》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、第42卷第2期哈爾濱工業(yè)大學學報Vol.42No.22010年2月JOURNALOFHARBININSTITUTEOFTECHNOLOGYFeb.2010R－樹和四叉樹的空間索引結構:RQOP樹－11，2劉潤濤，郝忠孝(1.哈爾濱理工大學計算機科學與技術學院，哈爾濱150080，liurt@hrbust.edu.cn;2.哈爾濱工業(yè)大學計算機科學與技術學院，哈爾濱150001)摘要:針對現(xiàn)有的基于R－樹和四叉樹的空間索引結構中存在的問題，通過建立數(shù)據(jù)矩形間的序關系對數(shù)據(jù)空間進行分割，提出了一種新的空間數(shù)據(jù)索引結構:RQOP樹.在此結
2、構中，節(jié)點的構造是按照空間數(shù)據(jù)的分布來進行的而不是像其它基于R－樹和四叉樹的空間索引結構只是對數(shù)據(jù)空間進行均勻劃分而得到，使樹的高度盡可能低，同時使兄弟節(jié)點間的交疊相對較小.在區(qū)域查詢算法中引入了查詢窗口包含節(jié)點MBR的判斷加快了查詢的速度.給出了RQOP樹的生成、節(jié)點插入和區(qū)域查詢算法，并給出了相應算法的可行性和正確性定理及時間復雜度分析.實驗表明:新索引結構的查詢速度明顯加快.關鍵詞:空間數(shù)據(jù);索引結構;RQOP樹;區(qū)域查詢中圖分類號:TP311文獻標志碼:A文章編號:0367－6234(2010)02－0323－05Spati
3、alindexstructurebasedonR-treeandquadtree:RQOP－tree11，2LIURun-tao，HAOZhong-xiao(1.CollegeofComputerScienceandTechnology，HarbinUniversityofScienceandTechnology，Harbin150080，China，liurt@hrbust.edu.cn;2.SchoolofComputerScienceandTechnology，HarbinInstituteofandTechnology，Ha
4、rbin150001，China)Abstract:Anewindexstructureforspatialdata，RQOP－tree，isproposedbysettinguptheorderrelationbe-tweendatarectanglestopartitionthedataspaces，aimedattheexistingproblemsincurrentindexstructuresbasedonR-treeandquadtree.Inthisstructure，themiddlenodesareconstruc
5、tedaccordingtothedistributionofspatialdatainsteadofpartitioningthedataspaceevenly，thereforetheheightofthetreeisguaranteedaslowaspossibleandacomparativelysmalloverlapbetweenbrothernodescanbekept.Intherangequeryalgo-rithm，thecheckofquerywindowcontaininganode’sMBRisintrod
6、ucedtospeedupthequeryeffectivelyforacomparativelylargequerywindow.Thealgorithmforconstructingtheindexstructureisgiven，anditstimecomplexityaswellasitscorrectnessispresented.Thealgorithmsfornodeinsertionandrangequeryareob-tained.Theexperimentshowsthatthequeryspeedisincre
7、asedgreatly.Keywords:spatialdata;indexstructure;RQOP_tree;rangequery空間數(shù)據(jù)索引技術是提高空間數(shù)據(jù)庫查詢性四叉樹，用于索引空間矩形數(shù)據(jù)的CIF－四叉［1］［2－3］*［4］［5－6］能的關鍵技術，直接影響到空間數(shù)據(jù)庫系統(tǒng)的性樹、QR－樹，QR－樹和PMR樹.能.四叉樹是一種層次結構，其結構清晰、易于實然而，這些索引結構在生成相應的索引結構時采現(xiàn)，廣泛用于很多領域.在空間數(shù)據(jù)庫中，將四叉用的是對數(shù)據(jù)空間進行四等分的分割或采用超節(jié)樹與R－樹結合得到的空間數(shù)據(jù)索引結構將用
8、于點策略.因此，當數(shù)據(jù)分布非均勻時，所產生的相索引空間數(shù)據(jù)點的點四叉樹、MX－四叉樹、PR－應的空間索引四叉樹將會是嚴重不平衡的，即，樹的高度將會變得很高，會嚴重地影響查詢的速度.收稿日期:2008－05－29.本文針對這一問題，結合
