1、隨著高維數(shù)據(jù)庫的快速發(fā)展，高維數(shù)據(jù)庫容量越來越大，為加快查詢效率，研究者已提出了多種對高維數(shù)據(jù)建立索引結(jié)構(gòu)的方法，但是這些索引結(jié)構(gòu)在如下兩個方面存在著缺陷:一方面，這些索引結(jié)構(gòu)大都是基于一個不合理的假設(shè)，即認為高維數(shù)據(jù)集中的數(shù)據(jù)都是均勻分布的，而且各個維之間相互獨立，不存在任何關(guān)聯(lián)性;另一方面，大部分的樹形索引結(jié)構(gòu)都有隨著維數(shù)升高而查詢性能下降的缺陷，已有研究表明，在維數(shù)大于10的情況下，會出現(xiàn)“維數(shù)災(zāi)難”現(xiàn)象。除了樹形索引結(jié)構(gòu)，向量近

2、似文件（VA-file及其改進等）有效地克服了“維數(shù)災(zāi)難”現(xiàn)象，但其查詢性能的加速被限制在很小的范圍內(nèi)，仍難以滿足實際的需要，而且它也是基于數(shù)據(jù)集中數(shù)據(jù)均勻分布，各維之間相互獨立的不合理的假設(shè)。
　　 自適應(yīng)聚類距離邊界面的高維索引方法基于高維空間中的數(shù)據(jù)非均勻分布，且每個維之間還存在著一定的關(guān)聯(lián)性的假設(shè)，這種假設(shè)符合真實數(shù)據(jù)集中數(shù)據(jù)的分布，因此它相比基于非真實數(shù)據(jù)集的高維索引結(jié)構(gòu)能更好的解決實際問題。自適應(yīng)聚類距離邊界面的高維

3、索引結(jié)構(gòu)采用生成Voronoi聚類的索引方法，這種索引方法放寬了聚類距離邊界面的規(guī)則性，放松的規(guī)則性更符合數(shù)據(jù)的原始分布，從而使得邊界面更加緊密。在基于此結(jié)構(gòu)的查詢中，可大大提高查詢效率。2011年有研究者將這種索引結(jié)構(gòu)與精確K近鄰查詢算法相結(jié)合，生成了適用于高維的基于自適應(yīng)聚類距離邊界的KNN查詢算法。這種查詢算法利用查詢向量到聚類距離邊界的下界值過濾掉不相關(guān)聚類的調(diào)入，很好的降低了I/O開銷。同時，在文章中研究者已通過相關(guān)實驗證實了

4、它相比基于順序掃描的索引如VA-File，iDistance，LDC索引結(jié)構(gòu)在降低I/O次數(shù)上具有更好的優(yōu)勢。因此基于此結(jié)構(gòu)的檢索算法具有更好的實用價值。但是，在基于此結(jié)構(gòu)的KNN查詢過程中仍需要計算查詢向量到聚類中所有對象的距離，這在維數(shù)很高，數(shù)據(jù)量很大的情況下會大大降低查詢性能，因此基于此結(jié)構(gòu)的KNN查詢算法仍有待改進。針對目前自適應(yīng)聚類距離邊界的高維索引結(jié)構(gòu)及相關(guān)查詢算法的現(xiàn)狀，本文在該領(lǐng)域進行了較深入的研究，主要工作和成果如下:

5、
　　 首先對相關(guān)高維檢索技術(shù)進行了綜述，研究了自適應(yīng)聚類距離邊界的高維索引結(jié)構(gòu)以及基于此結(jié)構(gòu)的KNN查詢算法，并分析了基于此結(jié)構(gòu)的查詢算法的不足;
　　 其次針對基于自適應(yīng)聚類距離邊界的高維索引的KNN查詢算法的不足，提出了改進的IV-KNN算法。通過在原來存儲結(jié)構(gòu)上增加一定的開銷和預(yù)處理，將三角不等式的思想應(yīng)用到基于自適應(yīng)聚類距離邊界的高維索引結(jié)構(gòu)的KNN查詢算法中，在原來降低I/O復(fù)雜度的基礎(chǔ)上，進一步降低了CPU

6、代價，提高了查詢性能。并通過在真實數(shù)據(jù)集上進行的實驗，驗證了這種改進的算法比原來的算法在查詢性能上有了較大的提高;
　　 最后從近似檢索的角度出發(fā)，綜合目前的近似檢索方法，提出采用LLE和PCA相結(jié)合的方法對數(shù)據(jù)集進行降維處理，然后再建立基于自適應(yīng)聚類距離邊界的高維索引結(jié)構(gòu)來實現(xiàn)近似檢索，提出了降維IV-KNN算法（RDIV-KNN），并基于真實數(shù)據(jù)集對算法的有效性和查詢效率進行了實驗，實驗結(jié)果表明RDIV-KNN查詢算法在查詢