多維空間數(shù)據(jù)庫NN檢索的并行處理方法.pdf

1、該文中采用了Roger Weber提出的VA-file的索引結(jié)構(gòu),其在高維環(huán)境下的檢索效率比R樹系列和X樹等索引結(jié)構(gòu)都高出了許多,特別是針對復(fù)雜的最鄰近檢索和相似性檢索.最鄰近檢索和相似性檢索(NN檢索)在多維空間數(shù)據(jù)庫中有十分重要的應(yīng)用,如GIS、CAD、多媒體數(shù)據(jù)、生物基因研究等領(lǐng)域.然而,實現(xiàn)多維的空間數(shù)據(jù)庫及各種多維的檢索卻存在許多困難.并且由于多維空間數(shù)據(jù)的檢索與傳統(tǒng)的關(guān)系模型數(shù)據(jù)庫有很大不同,通常的低維索引和檢索基于這樣一個

2、假設(shè):數(shù)據(jù)多在二級存儲器上,檢索代價是I/O相關(guān)的而不是CPU相關(guān)的.然而,這個假設(shè)在多維的空間數(shù)據(jù)庫管理中并不總是正確的,某些針對復(fù)雜對象的操作,(例如我們所涉及的NN檢索),會占用大量CPU的時間,從而改變與I/O的平衡<'[1]>.因此,多維檢索的效率不再主要決定于磁盤I/O的次數(shù).正是基于解決多維空間的最鄰近檢索的復(fù)雜性,該文在詳細分析多維空間檢索方法和一般并行檢索方法的基礎(chǔ)上,采用VA-file<'[2]>多維空間索引結(jié)構(gòu),結(jié)

3、合具體的NN檢索,從理論上引入一種基于VA-file的NN檢索的并行算法,采用前端處理器進行調(diào)度,通過輪轉(zhuǎn)法分配數(shù)據(jù)給后端處理器的方法并行運算.相對于VA-file的檢索算法,并行處理增加的復(fù)雜性和時間開銷集中于通信網(wǎng)絡(luò)的平均負載和前端處理機的控制代價,通過對其性能進行分析,結(jié)論是在數(shù)據(jù)量很大的情況下,通信網(wǎng)絡(luò)的負載加上前端處理機的控制代價,要小于每個處理器的平均處理時間.因此,一個合適的處理器數(shù)目所帶來的效率提高是準線性的.VA-fi