技術(shù)領(lǐng)域

本發(fā)明涉及信息檢索、數(shù)據(jù)挖掘以及聚類分析等數(shù)據(jù)處理領(lǐng)域，具體涉及到利用歐氏距離的上下界以及一定的數(shù)據(jù)結(jié)構(gòu)對高維數(shù)據(jù)進行索引并進行準確的近鄰查詢。?

背景技術(shù)

隨著信息技術(shù)和互聯(lián)網(wǎng)的蓬勃發(fā)展，多媒體數(shù)碼設(shè)備的廣泛使用，我們擁有了超越以往任何時代的海量網(wǎng)絡(luò)信息，而其中包含了大量的高維數(shù)據(jù)，如圖片，音頻，視頻等，如何對這種海量的高維數(shù)據(jù)進行快速準確的索引與檢索是一個亟待解決的難題。?

索引與檢索的一個重要作用就是近鄰查詢，即查詢出數(shù)據(jù)庫中與輸入數(shù)據(jù)最相似的數(shù)據(jù)，這是一種十分基礎(chǔ)但是重要的操作，除了信息檢索以外，還廣泛應(yīng)用于計算機視覺、機器學(xué)習(xí)等領(lǐng)域，高效與準確的近鄰查詢對這些前沿學(xué)科有著重要的應(yīng)用價值。?

傳統(tǒng)的近鄰查詢算法有著諸多不足，如采取空間劃分策略的k維樹，球樹等樹形結(jié)構(gòu)，它們對低維數(shù)據(jù)的效果較好，但當(dāng)數(shù)據(jù)維度較高時性能會急劇下滑；還有的處理高維數(shù)據(jù)的算法如局部敏感散列等，采取的是查詢近似近鄰的策略，效率較高但無法查詢準確的近鄰。本發(fā)明的主要貢獻在于提出了一種能夠快速的對高維數(shù)據(jù)查詢準確近鄰的方法。?

發(fā)明內(nèi)容

為了能夠針對高維數(shù)據(jù)進行快速準確的近鄰查詢，本發(fā)明提出了?一種基于歐氏距離上下界和數(shù)據(jù)過濾策略的高維近鄰查詢方法，該方法包括以下步驟：?

1、將數(shù)據(jù)表示成向量后，進行如下處理：?

1）將高維數(shù)據(jù)嵌入到以均值和方差構(gòu)成的二維空間S中，并采用制高點樹對嵌入后的二維數(shù)據(jù)建立索引，記為index1；?

2）為高維數(shù)據(jù)本身建立采樣近鄰索引，記為index2，該索引的建立可以采用任意近似近鄰索引結(jié)構(gòu)，如R樹，KD樹，局部敏感散列；?

3）對于查詢數(shù)據(jù)q，首先通過索引index2進行采樣，獲得閾值T，然后通過索引index1查詢出二維空間S上到q的歐氏距離小于T的數(shù)據(jù)點的集合，最后遍歷該集合并求出距離q最近的數(shù)據(jù)點。?

2、步驟1）中所述的索引index1的建立方法如下：?

1）將數(shù)據(jù)點嵌入到以均值和方差構(gòu)成的二維空間S中，具體方法為：若數(shù)據(jù)點??????????????????????????????????????????????????則嵌入后的點為(μ_x,σ_x)，其中μ_x和σ_x計算方法為???μx=1dΣi=1dxi,]]>σx=1dΣi=1d(xi-μx)2,]]>d為向量的維度；?

2）采用制高點樹對嵌入二維空間S后的數(shù)據(jù)集建立索引index1，其中制高點樹是一種適合范圍搜索的二叉樹結(jié)構(gòu)，在每個非葉子節(jié)點對數(shù)據(jù)進行劃分，作為劃分依據(jù)的是數(shù)據(jù)點到某一被選擇的制高點的距離，用制高點樹建立的索引能夠查詢到查詢點的歐氏距離小于某個?閾值的所有數(shù)據(jù)點；?

3、步驟3）中所述的近鄰查詢方法如下：?