本文關(guān)鍵詞：基于哈希算法的海量多媒體數(shù)據(jù)檢索研究，由筆耕文化傳播整理發(fā)布。

【摘要】：近鄰檢索問題是機(jī)器學(xué)習(xí)領(lǐng)域的一個基礎(chǔ)問題,在信息檢索、計算機(jī)視覺、數(shù)據(jù)挖掘等領(lǐng)域中都有著廣泛的應(yīng)用,例如以圖搜圖、人臉識別、k-means聚類等。近年來,隨著互聯(lián)網(wǎng)的快速發(fā)展,海量多媒體數(shù)據(jù)隨之而來。從多媒體數(shù)據(jù)中抽取出來的特征一般維度較高且稠密。如何對此類特征進(jìn)行高效檢索,成為了當(dāng)前學(xué)術(shù)界和工業(yè)界炙手可熱的研究內(nèi)容。目前,主流的近鄰檢索方法包括基于樹的方法和基于哈希的方法這兩種。其中,許多基于樹的近鄰檢索方法對特征空間進(jìn)行樹結(jié)構(gòu)的劃分,其時間復(fù)雜度和空間復(fù)雜度都以維度d作為指數(shù),所以當(dāng)維度d變大時,這些方法的效率就受到了限制。相反地,基于哈希算法的近鄰檢索方法是通過哈希函數(shù)(具有相似性保持的特性,即在原始特征空間中相似的兩個特征數(shù)據(jù)在映射到漢明空間后漢明距離也近)將一個d維的特征編碼成一個c位(一般地,c《d)的二進(jìn)制串,并通過漢明排序或者哈希表來進(jìn)行檢索。其中,漢明排序可以使用硬件(XOR)來進(jìn)行加速,而基于哈希表的檢索時間復(fù)雜度是O(1),與維度d無關(guān)。由于哈希算法具有高計算效率與維度不敏感的優(yōu)勢,其已經(jīng)引起了眾多學(xué)者和專家的研究興趣。圍繞基于哈希算法的海量多媒體數(shù)據(jù)近鄰檢索方法這一重要問題,本論文開展了以下工作：(1)面向高效檢索的哈希函數(shù)學(xué)習(xí)：基于哈希的近鄰檢索方法是以哈希函數(shù)為基礎(chǔ)的,一個好的哈希函數(shù)應(yīng)該能使用盡可能短的哈希編碼得到相對較高的準(zhǔn)確率�；陔S機(jī)投影的哈希算法不考慮數(shù)據(jù)的分布,需要較長位數(shù)的二進(jìn)制串才能獲得較好的近似性能。而基于學(xué)習(xí)的哈希算法從數(shù)據(jù)的分布中學(xué)習(xí)出投影向量,能在較短位數(shù)的二進(jìn)制串下獲得較好的性能。我們從衡量哈希函數(shù)的優(yōu)劣標(biāo)準(zhǔn)出發(fā),提出了一種基于學(xué)習(xí)的哈希算法一互補(bǔ)投影哈希算法。其是一個既保持?jǐn)?shù)據(jù)的近鄰性質(zhì)(保證檢索準(zhǔn)確率),又考慮哈希桶均衡性(保證檢索速度)的哈希函數(shù)學(xué)習(xí)方法。該算法的提出為基于哈希的高效檢索奠定了基礎(chǔ)。(2)跨媒體數(shù)據(jù)的哈希函數(shù)學(xué)習(xí)：海量多媒體(文本、圖像、視頻、音頻等)數(shù)據(jù)的出現(xiàn),使得面向跨媒體數(shù)據(jù)的哈希函數(shù)學(xué)習(xí)變得尤為重要。其要求學(xué)習(xí)出的哈希函數(shù)能夠使不同媒體之間的關(guān)聯(lián)體現(xiàn)在哈希編碼中,即具有相同概念的多媒體數(shù)據(jù)在編碼后應(yīng)具有相同的二進(jìn)制串。為此,我們提出了迭代多視角(Multi-View)哈希算法。其是一個同時保持同模態(tài)相似性和跨模態(tài)相似性的跨媒體哈希函數(shù)學(xué)習(xí)方法。其中,相似性的保持不止體現(xiàn)在對于相似數(shù)據(jù)要擁有相似的哈希編碼,也體現(xiàn)在不相似數(shù)據(jù)要擁有不相似的哈希編碼(獨特性)。該算法的提出為跨媒體數(shù)據(jù)的哈希函數(shù)學(xué)習(xí)提供了一個良好的優(yōu)化框架。(3)優(yōu)化的基于哈希表結(jié)構(gòu)的快速近鄰檢索：目前,相比基于樹結(jié)構(gòu)的近鄰檢索方法,基于哈希表的近鄰檢索方法未能展現(xiàn)出明顯的優(yōu)勢。其主要原因在于目前的哈希算法為了達(dá)到高準(zhǔn)確率和高召回率,通常需要擴(kuò)展?jié)h明半徑來進(jìn)行搜索,這使得檢索時間大大增加。為了消除這個瓶頸,我們提出了迭代擴(kuò)展哈希算法,其在線上使用一個輔助索引來對使用小漢明半徑檢索到的點做迭代擴(kuò)展,以此來保證高準(zhǔn)確率、高召回率和低檢索時間。該算法從本質(zhì)上提升了基于哈希表的近鄰檢索性能,為線上海量數(shù)據(jù)的實時搜索提供了有力保障。
【關(guān)鍵詞】：大數(shù)據(jù) 近鄰檢索 哈希算法
【學(xué)位授予單位】：浙江大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2015
【分類號】：TP181
【目錄】：

• 摘要5-7
• Abstract7-15
• 1 緒論15-21
• 1.1 研究背景和意義15-17
• 1.1.1 研究背景15-17
• 1.1.2 研究意義17
• 1.2 論文的研究內(nèi)容和目標(biāo)17-19
• 1.2.1 研究內(nèi)容17-18
• 1.2.2 研究目標(biāo)18-19
• 1.3 論文的組織結(jié)構(gòu)19-21
• 2 海量多媒體數(shù)據(jù)檢索研究現(xiàn)狀21-33
• 2.1 近鄰檢索問題21-22
• 2.2 基于樹結(jié)構(gòu)的近鄰檢索方法22-23
• 2.2.1 KD樹22
• 2.2.2 聚類樹22-23
• 2.2.3 其它樹結(jié)構(gòu)23
• 2.3 基于哈希的近鄰檢索方法23-31
• 2.3.1 局部敏感哈希24
• 2.3.2 單模態(tài)哈希算法24-30
• 2.3.3 多模態(tài)哈希算法30-31
• 2.4 基于kNN圖的近鄰搜索方法31
• 2.5 本章小結(jié)31-33
• 3 面向高效檢索的互補(bǔ)投影哈希算法33-47
• 3.1 引言33-35
• 3.2 與相關(guān)工作的區(qū)別35
• 3.3 算法35-41
• 3.3.1 穿越數(shù)據(jù)的稀疏區(qū)域35-36
• 3.3.2 近似均衡的哈希桶36-38
• 3.3.3 目標(biāo)函數(shù)38-39
• 3.3.4 譜松弛39
• 3.3.5 梯度下降39-40
• 3.3.6 計算復(fù)雜度分析40-41
• 3.4 實驗41-45
• 3.4.1 數(shù)據(jù)集41-42
• 3.4.2 實驗設(shè)置42-43
• 3.4.3 比較的哈希算法43
• 3.4.4 實驗結(jié)果與分析43-45
• 3.5 本章小結(jié)45-47
• 4 面向跨媒體數(shù)據(jù)索引的迭代多視角哈希算法47-65
• 4.1 引言47-48
• 4.2 記號48
• 4.3 算法48-53
• 4.3.1 視角內(nèi)相似性保持48-49
• 4.3.2 視角間的相似性保持49-50
• 4.3.3 目標(biāo)函數(shù)50-51
• 4.3.4 優(yōu)化方法51-53
• 4.4 實驗53-63
• 4.4.1 數(shù)據(jù)集54
• 4.4.2 實驗設(shè)置54-55
• 4.4.3 比較的方法55-56
• 4.4.4 Wiki上的跨模態(tài)檢索結(jié)果56-57
• 4.4.5 Flickr上的跨模態(tài)檢索結(jié)果57-58
• 4.4.6 Flickr上的單模態(tài)檢索結(jié)果58-59
• 4.4.7 訓(xùn)練效率59-61
• 4.4.8 參數(shù)敏感性61-62
• 4.4.9 收斂速度62-63
• 4.5 本章小結(jié)63-65
• 5 基于迭代擴(kuò)展哈希算法的優(yōu)化哈希表索引65-81
• 5.1 引言65-66
• 5.2 記號66
• 5.3 算法66-70
• 5.3.1 算法流程66-67
• 5.3.2 kNN表的動態(tài)更新67-68
• 5.3.3 線上階段的實現(xiàn)68-69
• 5.3.4 理論分析69-70
• 5.3.5 復(fù)雜度分析70
• 5.4 實驗70-79
• 5.4.1 數(shù)據(jù)集71
• 5.4.2 實驗設(shè)置71-72
• 5.4.3 與原始哈希方法的比較72-76
• 5.4.4 與多哈希表LSH的比較76-77
• 5.4.5 與KD樹的比較77-78
• 5.4.6 時間復(fù)雜度78-79
• 5.4.7 參數(shù)選擇79
• 5.5 本章小結(jié)79-81
• 6 總結(jié)與展望81-83
• 6.1 本文工作總結(jié)81-82
• 6.2 工作展望82-83
• 參考文獻(xiàn)83-97
• 攻讀博士學(xué)位期間主要的研究成果97-99
• 致謝99

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 陳一驕;盧錫城;孫志剛;;面向流管理的哈希算法研究[J];計算機(jī)工程與科學(xué);2008年04期

2 鄒保平;;基于一致哈希算法的用電信息采集系統(tǒng)研究[J];電力信息化;2011年06期

3 劉華珠;賀前華;;基于哈希算法的網(wǎng)絡(luò)橋接器地址維護(hù)方法(英文)[J];科學(xué)技術(shù)與工程;2008年17期

4 王遠(yuǎn);;可重構(gòu)哈希算法芯片的設(shè)計與實現(xiàn)[J];電腦知識與技術(shù);2012年04期

5 張江,傅鶴崗;基于關(guān)聯(lián)規(guī)則的二維哈希算法的改進(jìn)[J];計算機(jī)工程與設(shè)計;2005年08期

6 唐銘;史長瓊;周愷卿;張大方;;倒插入分段哈希算法[J];計算機(jī)應(yīng)用;2011年02期

7 孫陽;朱宏峰;劉天華;;一種新型抗旋轉(zhuǎn)攻擊的魯棒哈希算法[J];小型微型計算機(jī)系統(tǒng);2011年04期

8 賀賢明,邵雷兵;一種基于學(xué)習(xí)的自適應(yīng)哈希算法研究[J];計算機(jī)應(yīng)用與軟件;2004年11期

9 邵雷兵,莊毅;一種基于學(xué)習(xí)的自適應(yīng)哈希算法研究[J];微電子學(xué)與計算機(jī);2004年08期

10 陳青華;;一種新型的圖像哈希算法[J];兵工自動化;2011年05期

中國重要會議論文全文數(shù)據(jù)庫 前3條

1 劉宗斌;馬原;荊繼武;夏魯寧;;SM3哈希算法的硬件實現(xiàn)與研究[A];第26次全國計算機(jī)安全學(xué)術(shù)交流會論文集[C];2011年

2 文振q;朱為總;歐陽杰;高金花;;一種魯棒可區(qū)分的視頻感知哈希算法[A];第18屆全國多媒體學(xué)術(shù)會議（NCMT2009）、第5屆全國人機(jī)交互學(xué)術(shù)會議（CHCI2009）、第5屆全國普適計算學(xué)術(shù)會議（PCC2009）論文集[C];2009年

3 文振q;高金花;劉朋飛;杜以華;張萌;;基于分塊DCT和PCA的圖像感知哈希算法研究[A];第十五屆全國圖象圖形學(xué)學(xué)術(shù)會議論文集[C];2010年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前6條

1 金仲明;基于哈希算法的海量多媒體數(shù)據(jù)檢索研究[D];浙江大學(xué);2015年

2 焦玉華;音頻感知哈希算法研究[D];哈爾濱工業(yè)大學(xué);2010年

3 趙玉鑫;多媒體感知哈希算法及應(yīng)用研究[D];南京理工大學(xué);2009年

4 趙杠;對偶連接問題的哈希算法研究[D];復(fù)旦大學(xué);2010年

5 胡媛媛;基于視覺模型的圖像感知哈希算法研究[D];哈爾濱工業(yè)大學(xué);2011年

6 袁鑫攀;基于minwise哈希的文檔復(fù)制檢測的研究及應(yīng)用[D];中南大學(xué);2012年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 史世澤;局部敏感哈希算法的研究[D];西安電子科技大學(xué);2013年

2 林悅;基于哈希算法的高維數(shù)據(jù)的最近鄰檢索[D];浙江大學(xué);2013年

3 翁新釬;安全哈希算法的并行化實現(xiàn)研究[D];復(fù)旦大學(xué);2013年

4 張培超;基于隱變量模型的監(jiān)督式哈希算法[D];上海交通大學(xué);2014年

5 劉水生;感知哈希算法基準(zhǔn)測試平臺研究與設(shè)計[D];哈爾濱工業(yè)大學(xué);2008年

6 周權(quán);面向嵌入式安全哈希算法的研究與實現(xiàn)[D];湖南大學(xué);2013年

7 孫守興;基于可擴(kuò)展哈希算法的并行爬蟲動態(tài)負(fù)載均衡實現(xiàn)[D];哈爾濱工業(yè)大學(xué);2010年

8 周建輝;基于半監(jiān)督哈希算法的圖像檢索方法研究[D];大連理工大學(xué);2011年

9 曹姣;位置敏感哈希算法的性能分析研究[D];東華大學(xué);2014年

10 呂月明;基于非對稱哈希算法的大規(guī)模圖像檢索的研究[D];華南理工大學(xué);2015年

  本文關(guān)鍵詞：基于哈希算法的海量多媒體數(shù)據(jù)檢索研究，由筆耕文化傳播整理發(fā)布。

，

本文編號：438404