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

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

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

• 摘要4-5
• Abstract5-12
• 第1章 緒論12-19
• 1.1 選題背景和研究意義12
• 1.2 研究現(xiàn)狀及存在問(wèn)題12-15
• 1.2.1 國(guó)內(nèi)外研究現(xiàn)狀12-15
• 1.2.2 存在的問(wèn)題15
• 1.3 研究目標(biāo)和研究?jī)?nèi)容15-16
• 1.4 技術(shù)路線16-18
• 1.5 本文的組織結(jié)構(gòu)18-19
• 第2章 向量近似方法及其空間化擴(kuò)展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維護(hù)方法39-42
• 3.5 本章小結(jié)42-43
• 第4章 基于VAHSI的復(fù)合空間查詢實(shí)驗(yàn)與結(jié)果分析43-59
• 4.1 原型系統(tǒng)設(shè)計(jì)與實(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í)驗(yàn)數(shù)據(jù)45-47
• 4.2.1 開(kāi)發(fā)環(huán)境45
• 4.2.2 實(shí)驗(yàn)方案45-47
• 4.3 實(shí)驗(yàn)與結(jié)果分析47-58
• 4.4 本章小結(jié)58-59
• 第5章 結(jié)論與展望59-60
• 5.1 研究結(jié)論59
• 5.2 后續(xù)展望59-60
• 參考文獻(xiàn)60-65
• 致謝65

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：1072469