支持最近鄰查找的高維空間索引

《支持最近鄰查找的高維空間索引》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、復旦大學博士學位論文支持最近鄰查找的高維空間索引姓名：張軍旗申請學位級別：博士專業(yè)：計算機軟件與理論指導教師：施伯樂20070410論文獨創(chuàng)性聲明本論文是我個人在導師指導下進行的研究工作及取得的研究成果。論文中除了特別加以標注和致謝的地方外，不包含其他人或其它機構(gòu)已經(jīng)發(fā)表或撰寫過的研究成果。其他同志對本研究的啟發(fā)和所做的貢獻均已在論文中作了明確的聲明并表示了謝意。作者簽名：．麥量軍蘊論文使用授權(quán)聲明日期：塑!!Z：墨：，／本人完全了解復旦大學有關(guān)保留、使用學位論文的規(guī)定，即：學校有權(quán)保留送交論文的復印件，允許論文被查閱和借閱；學?？梢怨颊撐牡娜炕虿糠謨?nèi)容，可以采用影印、縮印

2、或其它復制手段保存論文。保密的論文在解密后遵守此規(guī)定。作者簽名：墨紅圣絲導師簽名：幺巡日期：竺!z：量z』復且大學博十畢業(yè)論文：支持最近鄰查找的高維空間索引張軍旗摘要在圖像、生物信息、醫(yī)學成像、時間序列等領(lǐng)域需要對大數(shù)據(jù)集進行相似性查詢。通過特征轉(zhuǎn)換將數(shù)據(jù)對象特征映射為高維向量空間的特征向量，把相似性查詢轉(zhuǎn)換為向量空間的最近鄰查詢，即給定查詢數(shù)據(jù)q及整數(shù)k，從數(shù)據(jù)庫中找出距離q最近的k個數(shù)據(jù)。為了提高查詢效率，研究者提出各種索引結(jié)構(gòu)管理特征向量。這些索引結(jié)構(gòu)在維數(shù)升高時性能會急劇下降，即“維災(zāi)”。針對高維數(shù)據(jù)索引結(jié)構(gòu)的現(xiàn)狀，我們在該領(lǐng)域進行了深入研究，取得了一定的成果。為了提高

3、索引的檢索效率，增強對高維的承受力，提出了多個具有良好性能的索引結(jié)構(gòu)，并提供了利用這些高維索引支持圖像相關(guān)反饋的方法。主要內(nèi)容如下：首先，為了對聚類與查詢性能之間的關(guān)系進行理論分析。提出一種新的基于聚類分解的高維度量空間B+一tree索引，它通過聚類分解對數(shù)據(jù)進行更細致的劃分來減少查詢的數(shù)據(jù)訪問。對聚類與查詢代價的關(guān)系進行了討論，通過查詢代價模型給出了最小查詢代價條件下的聚類分解數(shù)目等的理論計算公式。實驗顯示提出的索引方法明顯優(yōu)于iDistance等度量空間索引，最優(yōu)聚類分解數(shù)的估計接近實際最優(yōu)查詢時所需的聚類參數(shù)。然后，為了進一步改進高維數(shù)據(jù)庫查詢的效率。提出一種基于查詢采樣

4、進行數(shù)據(jù)分布估計的方法，并在此基礎(chǔ)上提出了一種支持最近鄰查詢的混合索引，即針對多媒體數(shù)據(jù)分布的不均勻性，有選擇的使用樹狀索引和順序掃描技術(shù)，建立統(tǒng)一的索引結(jié)構(gòu)。建立混合索引的具體步驟為：首先通過聚類分解分割數(shù)據(jù)并建立樹狀索引；然后使用查詢采樣算法，對數(shù)據(jù)實際分布進行估計；最后根據(jù)數(shù)據(jù)分布的特性，把稀疏數(shù)據(jù)從樹狀索引中剪裁出來進行基于順序掃描策略的索引，而分布比較密集的數(shù)據(jù)仍然保留在樹狀索引中。在五個真實的圖像數(shù)據(jù)集上進行了充分的實驗，結(jié)果顯示提出的索引方法明顯優(yōu)于iDistance等度量空間索引，在維數(shù)達到三百多維時查詢效率仍高于順序掃描。實驗結(jié)果還證明提出的查詢采樣算法在采樣

5、數(shù)據(jù)量僅為√Ⅳ(N為數(shù)據(jù)量)的情況下就可以獲得的滿足索引需要的分布估計結(jié)果。最后，為了使得提出的索引結(jié)構(gòu)能夠在圖像檢索中應(yīng)用，提出了利用高維索引支持用戶相關(guān)反饋的方法。關(guān)鍵詞：最近鄰查詢，采樣，高維索引結(jié)構(gòu)，邊緣數(shù)據(jù)，聚類分解復且大學博七畢業(yè)論文：支持最近鄰查找的高維審問索引張軍旗AbstractManyemergingdatabaseapplicationssuchasimage，timeseriesandscientificdatabases，manipulatehighdimensionaldata．Intheseapplications，Orleofthemostfre

6、quentlyusedandyetexpensiveoperationsistofindobjectsinthehigh-dimensionaldatabasethataresimilartoagivenqueryobject．Nearestneighborsearchisacentralrequirementinsuchcases．Thereisalongstr&dmofresearchonsolvingthenearestneighborsearchproblem,andalargenumberofmultidimensionalindexeshavebeendevelop

7、edforthispurpose．HowevertheseindexesturnworsewitIlthedimensiongrowth,whichiscalleddimensionalitycurse．Inordertoimprovethequeryefficiency,K-meansclusterapproachisoftenusedtoestimatethedatadistributioninthecontextofhighdimensionalmetricspaceindex．But