本文關(guān)鍵詞：面向大規(guī)模數(shù)據(jù)相似計(jì)算和搜索的哈希方法研究，，由筆耕文化傳播整理發(fā)布。

【摘要】：互聯(lián)網(wǎng)的發(fā)展帶來(lái)了數(shù)據(jù)的爆炸式增長(zhǎng)。如何在大規(guī)模數(shù)據(jù)中做基于相似度的計(jì)算和搜索是一個(gè)有廣闊應(yīng)用背景且具有挑戰(zhàn)性的基礎(chǔ)問(wèn)題,而具有局部敏感性質(zhì)的哈希方法則是一個(gè)有力的工具。局部敏感哈希方法將數(shù)據(jù)壓縮成緊湊的哈希碼,通過(guò)計(jì)算哈希碼間的某種簡(jiǎn)單距離(比如海明距離)即可快速估計(jì)出原始數(shù)據(jù)對(duì)間的相似度或者距離。這種保相似度的哈希碼作為對(duì)數(shù)據(jù)的一種壓縮表示,可以作為各種基于相似度的機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘算法的輸入,從而實(shí)現(xiàn)了存儲(chǔ)上的壓縮和計(jì)算上的加速。另一方面,也可以建立哈希表實(shí)現(xiàn)快速的相似搜索。目前有各種局部敏感哈希方法針對(duì)不同的數(shù)據(jù)類型和相似度定義�，F(xiàn)有的局部敏感哈希方法的估計(jì)方差較大,需要計(jì)算較多的哈希函數(shù)以保證一定的估計(jì)精度,從而帶來(lái)了較大的計(jì)算和存儲(chǔ)開(kāi)銷。本文首先針對(duì)具有簡(jiǎn)單結(jié)構(gòu)的數(shù)據(jù)——向量和集合,研究了相應(yīng)的局部敏感哈希方法。相對(duì)于局部敏感哈希使用獨(dú)立采樣的哈希函數(shù),本文提出使用結(jié)構(gòu)化采樣的哈希函數(shù),以降低估計(jì)的方差或者哈希時(shí)間。另一方面,之前的研究大多針對(duì)簡(jiǎn)單結(jié)構(gòu)的數(shù)據(jù),而很多實(shí)際數(shù)據(jù)并不能用簡(jiǎn)單結(jié)構(gòu)來(lái)表示,比如子空間、圖等。本文針對(duì)具有子空間結(jié)構(gòu)的數(shù)據(jù)提出了一種局部敏感哈希方法,并推廣到了三階張量類型的數(shù)據(jù)上。本文的創(chuàng)新點(diǎn)包括:1、針對(duì)向量類型的數(shù)據(jù),本文提出了超比特局部敏感哈希,使用結(jié)構(gòu)化采樣的哈希函數(shù)——分組正交化的隨機(jī)投影向量構(gòu)成的哈希函數(shù),作為對(duì)符號(hào)隨機(jī)投影哈希的改進(jìn)。本文證明了超比特局部敏感哈希可以提供對(duì)向量間角度的無(wú)偏估計(jì),并在理論上研究了由分組正交隨機(jī)投影向量構(gòu)成的哈希函數(shù)所帶來(lái)的方差的降低。實(shí)驗(yàn)驗(yàn)證了理論結(jié)果;2、對(duì)于集合類型的數(shù)據(jù),本文提出了最小最大值哈希方法,采用結(jié)構(gòu)化的哈希函數(shù)——最小值函數(shù)和最大值函數(shù),作為對(duì)最小值哈希的改進(jìn)。本文證明了最小最大值哈希在保證無(wú)偏估計(jì)的基礎(chǔ)上,將哈希時(shí)間降低到最小值哈希的一半,并且方差也略有降低;實(shí)驗(yàn)驗(yàn)證了理論結(jié)果;3、本文針對(duì)子空間和三階張量類型的數(shù)據(jù),提出了子空間保角哈希,并進(jìn)行了理論分析和實(shí)驗(yàn)驗(yàn)證。本文還提出了快速符號(hào)隨機(jī)投影方法和雙線性隨機(jī)投影方法用于加速子空間保角哈希的計(jì)算。
【關(guān)鍵詞】：局部敏感哈希 海明距離 相似搜索
【學(xué)位授予單位】：清華大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP391.3
【目錄】：

• 摘要3-4
• Abstract4-8
• 第1章 研究背景8-15
• 1.1 局部敏感哈希介紹9-11
• 1.1.1 局部敏感哈希函數(shù)族9-10
• 1.1.2 若干局部敏感哈希函數(shù)族簡(jiǎn)介10-11
• 1.2 局部敏感哈希研究概述11-12
• 1.3 論文結(jié)構(gòu)12-15
• 第2章 超比特局部敏感哈希15-49
• 2.1 研究動(dòng)機(jī)15-16
• 2.2 相關(guān)研究16-18
• 2.3 符號(hào)隨機(jī)投影哈希18-20
• 2.4 超比特局部敏感哈希20-22
• 2.5 理論分析22-39
• 2.5.1 無(wú)偏估計(jì)22-24
• 2.5.2 方差分析24-37
• 2.5.3 數(shù)值驗(yàn)證實(shí)驗(yàn)37-39
• 2.6 實(shí)驗(yàn)39-45
• 2.6.1 角度估計(jì)39-42
• 2.6.2 近似近鄰搜索42-45
• 2.7 本章總結(jié)45-49
• 第3章 最小最大值哈希49-71
• 3.1 研究動(dòng)機(jī)49-50
• 3.2 最小值哈希和K-最小值哈希50-55
• 3.2.1 最小值哈希50-54
• 3.2.2 K-最小值哈希54-55
• 3.3 關(guān)于最小值哈希和K-最小值哈希的方差分析55-57
• 3.3.1 K-最小值哈希的方差分析56-57
• 3.3.2 討論57
• 3.4 最小最大值哈希57-66
• 3.4.1 哈希時(shí)間分析60-61
• 3.4.2 估計(jì)的無(wú)偏性61
• 3.4.3 方差分析61-63
• 3.4.4 擴(kuò)展63-66
• 3.5 實(shí)驗(yàn)66-70
• 3.5.1 數(shù)據(jù)集66-67
• 3.5.2 杰卡德相似度估計(jì)67-68
• 3.5.3 近似近鄰搜索68-70
• 3.6 本章總結(jié)70-71
• 第4章 子空間保角哈希71-95
• 4.1 研究動(dòng)機(jī)71-73
• 4.2 相關(guān)研究73
• 4.3 子空間的相似度定義73-76
• 4.3.1 子空間之間的主角73-74
• 4.3.2 子空間的角度、角度相似度和角度距離74-76
• 4.4 保持角度相似度的子空間哈希方法76-81
• 4.5 加速隨機(jī)投影的計(jì)算81-86
• 4.5.1 快速符號(hào)隨機(jī)投影81-84
• 4.5.2 雙線性隨機(jī)投影84-86
• 4.6 實(shí)驗(yàn)86-93
• 4.6.1 人臉識(shí)別86-90
• 4.6.2 手勢(shì)和動(dòng)作識(shí)別90-93
• 4.7 本章總結(jié)93-95
• 第5章 總結(jié)與展望95-99
• 參考文獻(xiàn)99-105
• 致謝105-107
• 個(gè)人簡(jiǎn)歷、在學(xué)期間發(fā)表的學(xué)術(shù)論文與研究成果107

【相似文獻(xiàn)】

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

1 張勇,雷振明;基于流應(yīng)用中的哈希查表性能研究[J];計(jì)算機(jī)工程與應(yīng)用;2003年25期

2 馬如林;蔣華;張慶霞;;一種哈希表快速查找的改進(jìn)方法[J];計(jì)算機(jī)工程與科學(xué);2008年09期

3 蔣大宏;動(dòng)態(tài)哈希方法[J];計(jì)算機(jī)工程;1993年01期

4 蔣大宏;實(shí)現(xiàn)檢索代價(jià)最優(yōu)的動(dòng)態(tài)哈希法[J];計(jì)算機(jī)工程與應(yīng)用;1994年Z2期

5 劉冠福;;動(dòng)態(tài)哈希表的設(shè)計(jì)及應(yīng)用[J];計(jì)算機(jī)時(shí)代;1996年02期

6 朱芳芳;李訓(xùn)根;;改進(jìn)的哈希表查找算法[J];杭州電子科技大學(xué)學(xué)報(bào);2013年05期

7 趙宇;;基于哈希表查找方法的優(yōu)勢(shì)及其算法的改進(jìn)[J];中小企業(yè)管理與科技(下旬刊);2012年03期

8 高文利;朱麗;;哈希表在計(jì)算語(yǔ)言學(xué)中的運(yùn)用[J];現(xiàn)代語(yǔ)文(語(yǔ)言研究版);2009年06期

9 賀元香;史寶明;;除留余數(shù)法建立哈希表的方法改進(jìn)[J];甘肅科技;2008年07期

10 劉艙強(qiáng);鄧昌勝;余諒;;基于哈希表的最長(zhǎng)前綴匹配算法改進(jìn)[J];微計(jì)算機(jī)信息;2009年30期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前2條

1 朱芳芳;李訓(xùn)根;;改進(jìn)的哈希表查找算法[A];浙江省電子學(xué)會(huì)2013學(xué)術(shù)年會(huì)論文集[C];2013年

2 趙競(jìng);余宏亮;張X;鄭緯民;;廣域網(wǎng)分布式哈希表存儲(chǔ)副本可靠性的維護(hù)[A];全國(guó)網(wǎng)絡(luò)與信息安全技術(shù)研討會(huì)論文集（下冊(cè)）[C];2007年

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

1 黃慧群;內(nèi)容中心網(wǎng)絡(luò)的查表技術(shù)研究[D];解放軍信息工程大學(xué);2014年

2 季劍秋;面向大規(guī)模數(shù)據(jù)相似計(jì)算和搜索的哈希方法研究[D];清華大學(xué);2015年

3 彭建章;非阻塞算法與多進(jìn)程網(wǎng)絡(luò)程序優(yōu)化研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2013年

4 付海燕;基于圖像哈希的大規(guī)模圖像檢索方法研究[D];大連理工大學(xué);2014年

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

1 郝廣洋;語(yǔ)音感知哈希及其在密文語(yǔ)音檢索中的應(yīng)用研究[D];西南交通大學(xué);2015年

2 黃志騫;基于迭代量化的用于近似最近鄰檢索的哈希方法[D];華南理工大學(xué);2015年

3 王聰;基于局部敏感哈希的聲源定位方法[D];大連理工大學(xué);2015年

4 鄧慧茹;面向大規(guī)模視覺(jué)檢索的哈希學(xué)習(xí)[D];西安電子科技大學(xué);2014年

5 張梁;基于局部敏感哈希的近似近鄰查詢算法研究[D];南京郵電大學(xué);2015年

6 盧佳音;基于圖像哈希檢索的圖像重排方法研究[D];大連理工大學(xué);2013年

7 汪龍重;達(dá)夢(mèng)數(shù)據(jù)庫(kù)哈希連接算法的研究[D];華中科技大學(xué);2012年

8 楊牧洲;分層哈希鏈表及其在數(shù)據(jù)查詢認(rèn)證中的應(yīng)用[D];東北大學(xué);2009年

9 陳凱;數(shù)據(jù)庫(kù)哈希連接算法研究[D];復(fù)旦大學(xué);2013年

10 李洋;基于自學(xué)哈希的信息檢索[D];吉林大學(xué);2015年

  本文關(guān)鍵詞：面向大規(guī)模數(shù)據(jù)相似計(jì)算和搜索的哈希方法研究，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：406756