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

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

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

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