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

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

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