基于VAR-樹(shù)的反向最近鄰查詢技術(shù)的研究.pdf

1、在空間數(shù)據(jù)庫(kù)中，反向最近鄰查詢技術(shù)是最重要的查詢技術(shù)之一，它是在最近鄰查詢技術(shù)的基礎(chǔ)上提出的，反向最近鄰查詢技術(shù)是空間數(shù)據(jù)庫(kù)技術(shù)研究的重點(diǎn)和難點(diǎn)，如何有效地實(shí)現(xiàn)反向最近鄰查詢一直是人們研究的熱點(diǎn)問(wèn)題。目前對(duì)反向最近鄰查詢的研究還不是很多，它們都存在著一定的缺陷，比如查詢效率不高，不適合高維空間的查詢等等。本文對(duì)目前國(guó)內(nèi)外反向最近鄰查詢的研究成果進(jìn)行分析，在原有研究的基礎(chǔ)上提出了本文的觀點(diǎn)，主要內(nèi)容包括以下幾個(gè)方面;
　　 ⑴為了

2、有效地實(shí)現(xiàn)反向最近鄰查詢，本文提出了一種新的索引結(jié)構(gòu)VAR*-Tree。VAR*樹(shù)是在原有的VAR樹(shù)的基礎(chǔ)上做了改進(jìn)，引入了性能優(yōu)良的SR樹(shù)。VAR*樹(shù)的構(gòu)造過(guò)程主要包括對(duì)原始數(shù)據(jù)的量化壓縮和把量化壓縮后的近似數(shù)據(jù)用SR樹(shù)來(lái)進(jìn)行管理（用近似數(shù)據(jù)構(gòu)造一棵SR樹(shù)）兩個(gè)步驟。這種索引結(jié)構(gòu)的優(yōu)點(diǎn)是對(duì)原始數(shù)據(jù)的量化壓縮能夠大大減少存儲(chǔ)空間，引入的SR樹(shù)的索引結(jié)構(gòu)也更加適合反向最近鄰查詢的要求。經(jīng)實(shí)驗(yàn)驗(yàn)證，VAR*樹(shù)的索引結(jié)構(gòu)較SR樹(shù)索引結(jié)構(gòu)占用空

3、間更小、更適合查詢的需要。
　　 ⑵在VAR*樹(shù)的基礎(chǔ)上給出了基于VAR*樹(shù)的最近鄰查詢算法VAR*NN算法，還給出了基于VAR*樹(shù)的KNN算法。算法經(jīng)實(shí)驗(yàn)驗(yàn)證查詢效率優(yōu)于以往的最近鄰查詢算法。
　　 ⑶在VAR*樹(shù)的基礎(chǔ)上給出了基于VAR*樹(shù)的反向最近鄰查詢算法VAR*RNN算法，還給出了VAR*RNN算法相關(guān)的插入和刪除算法。經(jīng)實(shí)驗(yàn)驗(yàn)證算法在2維和11維的空間下，查詢效率優(yōu)于以往的反向最近鄰查詢算法。