基于向量近似的復(fù)合空間索引研究.pdf

1、隨著對(duì)地觀測(cè)手段的不斷發(fā)展，人類(lèi)獲取空間數(shù)據(jù)的能力達(dá)到空前的水平?？焖贉?zhǔn)確地從海量空間數(shù)據(jù)中獲取有效的信息，既是GIS可用性的前提，也是對(duì)空間數(shù)據(jù)進(jìn)一步分析應(yīng)用的基礎(chǔ)。復(fù)合空間查詢(xún)是一種常用的空間查詢(xún)方式，通過(guò)幾何與屬性條件復(fù)合進(jìn)行查詢(xún)以獲取用戶(hù)需要的空間信息。為了提高復(fù)合空間查詢(xún)的效率，一般通過(guò)空間索引和屬性索引進(jìn)行剪枝，但由于需要在不同字段上分別建立索引，一方面增加了索引維護(hù)的復(fù)雜性，降低了存儲(chǔ)效率，另一方面割裂了特征間可能存在的相

2、關(guān)性，降低了查詢(xún)效率。
　　本文提出一種復(fù)合空間索引，該索引引入向量近似思想并進(jìn)行空間化擴(kuò)展，利用特征間的相關(guān)性實(shí)現(xiàn)對(duì)幾何與屬性特征同時(shí)剪枝，借助二進(jìn)制位向量和計(jì)算機(jī)高效的位運(yùn)算能力，實(shí)現(xiàn)了較高的查詢(xún)效率和較低的存儲(chǔ)開(kāi)銷(xiāo)。尤其需要指出，該索引無(wú)需建立基于MBR的空間索引結(jié)構(gòu)，通過(guò)隱式空間剪枝即可實(shí)現(xiàn)更精確的空間過(guò)濾。
　　論文的主要研究?jī)?nèi)容和成果如下:
　　(1)提出了向量近似空間化擴(kuò)展方法。論文對(duì)比分析了均勻劃分和非

3、均勻劃分對(duì)查詢(xún)效率的影響，提出了在幾何和屬性特征上建立非均勻劃分的優(yōu)化劃分方案，并采用向量近似思想將空間數(shù)據(jù)的多維特征映射到一維線性空間中。該擴(kuò)展方法具有低存儲(chǔ)和高性能等優(yōu)點(diǎn)。
　　(2)提出了一種基于向量近似的復(fù)合空間索引(VAHSI，VectorApproximation based Hybrid Spatial Index)。該索引基于空間化向量近似思想把空間數(shù)據(jù)集映射為一系列數(shù)據(jù)桶。在一級(jí)過(guò)濾層，基于計(jì)數(shù)排序思想，建立了空

4、間數(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ù)密度，分別采用位向量和枚舉法建立桶索引。查詢(xún)時(shí)首先對(duì)查詢(xún)條件進(jìn)行分解，通過(guò)高速映射表高速剪枝，然后利用桶索引和位運(yùn)算進(jìn)行二次快速剪枝以獲得更精煉的候選數(shù)據(jù)集，最后對(duì)候選數(shù)據(jù)集進(jìn)行精確過(guò)濾。論文給出了該復(fù)合空間索引的查詢(xún)、插入和刪除算法。
　　(3)構(gòu)建了基于VAHSI的復(fù)合空間查詢(xún)?cè)拖到y(tǒng)，在