基于數(shù)據(jù)轉(zhuǎn)化的k近鄰查詢算法研究.pdf

1、k近鄰查詢算法在地理信息系統(tǒng)、圖像數(shù)據(jù)庫和生物信息學(xué)等領(lǐng)域有著廣泛的應(yīng)用。因此，有效地處理k近鄰查詢成為商業(yè)多媒體數(shù)據(jù)庫的研究熱點(diǎn)之一。本文主要對利用數(shù)據(jù)轉(zhuǎn)化方法提高k近鄰查詢算法的問題進(jìn)行研究，主要內(nèi)容如下：
　　首先，目前主流的數(shù)據(jù)庫是以R樹索引最小外包矩形的形式存儲數(shù)據(jù)，而基于L1距離的范圍查詢在進(jìn)行距離計算時，會產(chǎn)生菱形的查詢框。在查詢過程中，菱形查詢框與矩形節(jié)點(diǎn)之間的幾何沖突導(dǎo)致計算過程復(fù)雜、查詢效率低等問題。因此提出了

2、一種數(shù)據(jù)轉(zhuǎn)化技術(shù)，將一種特征空間轉(zhuǎn)化為另一種特征空間，從而使原空間中的范圍查詢轉(zhuǎn)化為轉(zhuǎn)化后空間中的矩形查詢。對于二維空間轉(zhuǎn)化是精確的，但是多維轉(zhuǎn)化會產(chǎn)生假正現(xiàn)象。針對多維轉(zhuǎn)化查詢結(jié)果不精確這一問題，提出了一種修正矩形查詢算法，并給出了算法的實(shí)現(xiàn)過程。同時給出了轉(zhuǎn)化的理論模型，通過詳細(xì)的理論分析，說明了轉(zhuǎn)化后的矩形查詢具有更好的查詢性能。
　　其次，通過分析說明了k近鄰查詢可以看做是一種特殊的范圍查詢，該數(shù)據(jù)轉(zhuǎn)化技術(shù)對k近鄰查詢同樣