本文關鍵詞：基于向量近似的復合空間索引研究

  更多相關文章： 向量近似 復合空間索引 復合空間查詢 非均勻劃分

【摘要】：隨著對地觀測手段的不斷發(fā)展,人類獲取空間數(shù)據(jù)的能力達到空前的水平。快速準確地從海量空間數(shù)據(jù)中獲取有效的信息,既是GIS可用性的前提,也是對空間數(shù)據(jù)進一步分析應用的基礎。復合空間查詢是一種常用的空間查詢方式,通過幾何與屬性條件復合進行查詢以獲取用戶需要的空間信息。為了提高復合空間查詢的效率,一般通過空間索引和屬性索引進行剪枝,但由于需要在不同字段上分別建立索引,一方面增加了索引維護的復雜性,降低了存儲效率,另一方面割裂了特征間可能存在的相關性,降低了查詢效率。本文提出一種復合空間索引,該索引引入向量近似思想并進行空間化擴展,利用特征間的相關性實現(xiàn)對幾何與屬性特征同時剪枝,借助二進制位向量和計算機高效的位運算能力,實現(xiàn)了較高的查詢效率和較低的存儲開銷。尤其需要指出,該索引無需建立基于MBR的空間索引結構,通過隱式空間剪枝即可實現(xiàn)更精確的空間過濾。論文的主要研究內(nèi)容和成果如下：(1)提出了向量近似空間化擴展方法。論文對比分析了均勻劃分和非均勻劃分對查詢效率的影響,提出了在幾何和屬性特征上建立非均勻劃分的優(yōu)化劃分方案,并采用向量近似思想將空間數(shù)據(jù)的多維特征映射到一維線性空間中。該擴展方法具有低存儲和高性能等優(yōu)點。(2)提出了一種基于向量近似的復合空間索引(VAHSI, Vector Approximation based Hybrid Spatial Index)。該索引基于空間化向量近似思想把空間數(shù)據(jù)集映射為一系列數(shù)據(jù)桶。在一級過濾層,基于計數(shù)排序思想,建立了空間數(shù)據(jù)集與數(shù)據(jù)桶的高速映射表,基于該高速映射表,無需任何輔助結構,可以實現(xiàn)在O(1)時間內(nèi)對數(shù)據(jù)桶的直接定位；在二級索引層,根據(jù)數(shù)據(jù)桶的數(shù)據(jù)密度,分別采用位向量和枚舉法建立桶索引。查詢時首先對查詢條件進行分解,通過高速映射表高速剪枝,然后利用桶索引和位運算進行二次快速剪枝以獲得更精煉的候選數(shù)據(jù)集,最后對候選數(shù)據(jù)集進行精確過濾。論文給出了該復合空間索引的查詢、插入和刪除算法。(3)構建了基于VAHSI的復合空間查詢原型系統(tǒng),在此基礎上進行了一系列對比實驗,對實驗結果的分析表明,本文提出的復合空間索引具有高性能和低存儲開銷的特性。
【關鍵詞】：向量近似 復合空間索引 復合空間查詢 非均勻劃分
【學位授予單位】：南京師范大學
【學位級別】：碩士
【學位授予年份】：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 研究目標和研究內(nèi)容15-16
• 1.4 技術路線16-18
• 1.5 本文的組織結構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 幾何與屬性特征復合映射規(guī)則26-27
• 2.5 本章小結27-28
• 第3章 基于向量近似的復合空間索引VAHSI28-43
• 3.1 VAHSI索引結構28-29
• 3.2 VAHSI構建方法29-35
• 3.3 VAHSI索引方法35-39
• 3.4 VAHSI維護方法39-42
• 3.5 本章小結42-43
• 第4章 基于VAHSI的復合空間查詢實驗與結果分析43-59
• 4.1 原型系統(tǒng)設計與實現(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 實驗與結果分析47-58
• 4.4 本章小結58-59
• 第5章 結論與展望59-60
• 5.1 研究結論59
• 5.2 后續(xù)展望59-60
• 參考文獻60-65
• 致謝65

【參考文獻】

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

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

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

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

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

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

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

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

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

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

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

，

本文編號：1072469