本文關(guān)鍵詞：基于向量近似的復(fù)合空間索引研究

  更多相關(guān)文章： 向量近似 復(fù)合空間索引 復(fù)合空間查詢 非均勻劃分

【摘要】：隨著對地觀測手段的不斷發(fā)展,人類獲取空間數(shù)據(jù)的能力達到空前的水平�？焖贉�(zhǔn)確地從海量空間數(shù)據(jù)中獲取有效的信息,既是GIS可用性的前提,也是對空間數(shù)據(jù)進一步分析應(yīng)用的基礎(chǔ)。復(fù)合空間查詢是一種常用的空間查詢方式,通過幾何與屬性條件復(fù)合進行查詢以獲取用戶需要的空間信息。為了提高復(fù)合空間查詢的效率,一般通過空間索引和屬性索引進行剪枝,但由于需要在不同字段上分別建立索引,一方面增加了索引維護的復(fù)雜性,降低了存儲效率,另一方面割裂了特征間可能存在的相關(guān)性,降低了查詢效率。本文提出一種復(fù)合空間索引,該索引引入向量近似思想并進行空間化擴展,利用特征間的相關(guān)性實現(xiàn)對幾何與屬性特征同時剪枝,借助二進制位向量和計算機高效的位運算能力,實現(xiàn)了較高的查詢效率和較低的存儲開銷。尤其需要指出,該索引無需建立基于MBR的空間索引結(jié)構(gòu),通過隱式空間剪枝即可實現(xiàn)更精確的空間過濾。論文的主要研究內(nèi)容和成果如下：(1)提出了向量近似空間化擴展方法。論文對比分析了均勻劃分和非均勻劃分對查詢效率的影響,提出了在幾何和屬性特征上建立非均勻劃分的優(yōu)化劃分方案,并采用向量近似思想將空間數(shù)據(jù)的多維特征映射到一維線性空間中。該擴展方法具有低存儲和高性能等優(yōu)點。(2)提出了一種基于向量近似的復(fù)合空間索引(VAHSI, Vector Approximation based Hybrid Spatial Index)。該索引基于空間化向量近似思想把空間數(shù)據(jù)集映射為一系列數(shù)據(jù)桶。在一級過濾層,基于計數(shù)排序思想,建立了空間數(shù)據(jù)集與數(shù)據(jù)桶的高速映射表,基于該高速映射表,無需任何輔助結(jié)構(gòu),可以實現(xiàn)在O(1)時間內(nèi)對數(shù)據(jù)桶的直接定位；在二級索引層,根據(jù)數(shù)據(jù)桶的數(shù)據(jù)密度,分別采用位向量和枚舉法建立桶索引。查詢時首先對查詢條件進行分解,通過高速映射表高速剪枝,然后利用桶索引和位運算進行二次快速剪枝以獲得更精煉的候選數(shù)據(jù)集,最后對候選數(shù)據(jù)集進行精確過濾。論文給出了該復(fù)合空間索引的查詢、插入和刪除算法。(3)構(gòu)建了基于VAHSI的復(fù)合空間查詢原型系統(tǒng),在此基礎(chǔ)上進行了一系列對比實驗,對實驗結(jié)果的分析表明,本文提出的復(fù)合空間索引具有高性能和低存儲開銷的特性。
【關(guān)鍵詞】：向量近似 復(fù)合空間索引 復(fù)合空間查詢 非均勻劃分
【學(xué)位授予單位】：南京師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：P208
【目錄】：

• 摘要4-5
• Abstract5-12
• 第1章 緒論12-19
• 1.1 選題背景和研究意義12
• 1.2 研究現(xiàn)狀及存在問題12-15
• 1.2.1 國內(nèi)外研究現(xiàn)狀12-15
• 1.2.2 存在的問題15
• 1.3 研究目標(biāo)和研究內(nèi)容15-16
• 1.4 技術(shù)路線16-18
• 1.5 本文的組織結(jié)構(gòu)18-19
• 第2章 向量近似方法及其空間化擴展19-28
• 2.1 向量近似方法研究19-20
• 2.2 屬性特征映射規(guī)則20-24
• 2.2.1 屬性特征均勻映射20-21
• 2.2.2 屬性特征非均勻映射21-24
• 2.3 幾何特征映射規(guī)則24-26
• 2.3.1 幾何特征均勻映射24-25
• 2.3.2 幾何特征非均勻映射25-26
• 2.4 幾何與屬性特征復(fù)合映射規(guī)則26-27
• 2.5 本章小結(jié)27-28
• 第3章 基于向量近似的復(fù)合空間索引VAHSI28-43
• 3.1 VAHSI索引結(jié)構(gòu)28-29
• 3.2 VAHSI構(gòu)建方法29-35
• 3.3 VAHSI索引方法35-39
• 3.4 VAHSI維護方法39-42
• 3.5 本章小結(jié)42-43
• 第4章 基于VAHSI的復(fù)合空間查詢實驗與結(jié)果分析43-59
• 4.1 原型系統(tǒng)設(shè)計與實現(xiàn)43-45
• 4.1.1 核心類43
• 4.1.2 系統(tǒng)功能43-44
• 4.1.3 系統(tǒng)界面44-45
• 4.2 實驗數(shù)據(jù)45-47
• 4.2.1 開發(fā)環(huán)境45
• 4.2.2 實驗方案45-47
• 4.3 實驗與結(jié)果分析47-58
• 4.4 本章小結(jié)58-59
• 第5章 結(jié)論與展望59-60
• 5.1 研究結(jié)論59
• 5.2 后續(xù)展望59-60
• 參考文獻60-65
• 致謝65

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前4條

1 董道國;劉振中;薛向陽;;VA-Trie:一種用于近似k近鄰查詢的高維索引結(jié)構(gòu)[J];計算機研究與發(fā)展;2005年12期

2 劉云生,王洪庭,廖國瓊;利用HB+樹的復(fù)合索引問題的解決方案[J];計算機工程;2005年17期

3 徐少平;王命延;王煒立;;一種基于R樹和四叉樹的移動對象空間數(shù)據(jù)庫混合索引結(jié)構(gòu)[J];計算機與數(shù)字工程;2006年03期

4 胡廷波;鐘俊;;基于分簇的B~+樹數(shù)據(jù)庫索引優(yōu)化算法[J];計算機應(yīng)用;2013年09期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 龍柏;并行計算平臺上的數(shù)據(jù)索引技術(shù)研究[D];中國科學(xué)技術(shù)大學(xué);2011年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前3條

1 古毅;基于內(nèi)容的圖像檢索中索引技術(shù)的研究及系統(tǒng)實現(xiàn)[D];重慶大學(xué);2006年

2 郭娟;基于自適應(yīng)聚類距離邊界的高維檢索算法研究[D];浙江工業(yè)大學(xué);2012年

3 肖圓秀;云計算環(huán)境下海量GML空間數(shù)據(jù)存儲索引機制研究[D];江西理工大學(xué);2013年

，

本文編號：1072469