集合作為一種高效的數(shù)據(jù)表示手段,已經(jīng)應(yīng)用于很多領(lǐng)域,例如可用于表示用戶聽音樂的喜好,購物網(wǎng)站的商品,生物信息工程中的基因序列等。近年來,隨著電子商務(wù)、信息檢索、生物信息工程等領(lǐng)域的快速發(fā)展,數(shù)據(jù)集合的規(guī)模和復(fù)雜度不斷增大�？焖偬幚砗Ａ壳覐�(fù)雜的集合相似度數(shù)據(jù)已是近年研究的熱點(diǎn)。在相似度查詢計(jì)算中,往往會(huì)存在一些因?yàn)榧祥L度太長、或者太短導(dǎo)致兩個(gè)集合完全不可能滿足給定的相似度閾值的情況,對這些集合進(jìn)行過濾或計(jì)算時(shí)消耗了大量的不必要的時(shí)間與空間。為解決此問題,本文首先提出一種基于長度分區(qū)的集合相似度查詢方法。將長度分區(qū)的思想與經(jīng)典的相似度查詢算法ScanCount相結(jié)合,通過數(shù)據(jù)預(yù)處理、長度分區(qū)及高效的索引結(jié)構(gòu)LenSegII（Length Segmented Invert Indexes）快速過濾不可能相似度的記錄,從而提升算法效率。此外,設(shè)計(jì)更為精簡的計(jì)數(shù)數(shù)組,從而降低了空間開銷。在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)表明本方法具有更高的時(shí)間和空間效率�，F(xiàn)今大多數(shù)集合相似度查詢算法都是以CPU串行或CPU并行掃描倒排列表的方式工作的,因而效率以及吞吐量都比較低,難以適應(yīng)大規(guī)模及超大規(guī)模集合的快速相似度查詢... 

【文章來源】：昆明理工大學(xué)云南省

【文章頁數(shù)】：68 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

GPU和CPU每秒浮點(diǎn)操作數(shù)

昆明理工大學(xué)碩士學(xué)位論文8圖1.2GPU和CPU存儲(chǔ)器帶寬文獻(xiàn)[41]介紹了雙調(diào)排序在集合相似度中的運(yùn)用。文獻(xiàn)[42]提出了在圖形處理單元（GPU）上的有效集合相似度連接的方案。提出了一種在GPU上集合相似度連接的新方案：使用MinHash來估計(jì)兩集合間的Jaccard相似度。其主要思想是基于每個(gè)集合的元素創(chuàng)建簽名，然后比較簽名以估計(jì)其Jaccard相似性。如果兩個(gè)集合具有許多一致的簽名部分，則它們具有一定程度的相似性。以這種方式，可以在不對所有元素進(jìn)行耗時(shí)的掃描的同時(shí)估計(jì)Jaccard相似度。此外，只需要存儲(chǔ)簽名而不是存儲(chǔ)集合的所有元素，這也極大地有助于減少存儲(chǔ)空間。通過利用GPU的高并行性和MinHash提供的空間效率，可以實(shí)現(xiàn)高性能并且不犧牲太多準(zhǔn)確性。實(shí)驗(yàn)結(jié)果表明，該方法比串行版本的CPU實(shí)現(xiàn)方法快兩個(gè)數(shù)量級(jí)，比并行版本的CPU實(shí)現(xiàn)方法快25倍，同時(shí)可以生成高度精確的查詢結(jié)果。ZhouJ等人[44]提出了一套可針對不同數(shù)據(jù)類型進(jìn)行并行集合相似度搜索的通用倒排索引框架，同時(shí)并提出了一種新的局部敏感哈希處理方式。GalletB等人[51]提出了幾種降低GPU相似度自連接算法負(fù)載不均衡的方法。由于數(shù)據(jù)依賴性等問題，使得系統(tǒng)分配給線程的工作負(fù)載存在差異。通過考慮分配給每個(gè)線程的總工作負(fù)載，并強(qiáng)制GPU的硬件調(diào)度程序在同一個(gè)warp中對具有類似工作負(fù)載的線程進(jìn)行分組，從而減少線程間的負(fù)載不平衡情況。ChauhanSS[52]等人提出了一種使用布隆過濾器（Bloomfilters）來進(jìn)行并行相似性查詢方法，該方法使用布隆過濾器來表示文檔的特征并與用戶的查詢進(jìn)行比較。FengY[53]等人提出了一種在GPU上的、基于前向列表和反向列表的并行文檔相似性自連接算法，該算法分兩步分別執(zhí)行文檔不同部分來計(jì)算文檔的相似

現(xiàn)。實(shí)際上，Li[24]等人已經(jīng)將 MinHash 與 GPU 的并行計(jì)算能力的組合，在他們的在線學(xué)習(xí)應(yīng)用程序中，處理時(shí)間至少減少了一個(gè)數(shù)量級(jí)以上。2.6 GPU 結(jié)構(gòu)與線程網(wǎng)絡(luò)GPU 與 CPU 的不同之處在于：普通 CPU 核心數(shù)為 2 或 4 核，而 GPU 的核心數(shù)則普遍在 1000 核心以上，所以 GPU 可以其同時(shí)運(yùn)行成千上萬的線程，遠(yuǎn)超一般 CPU，本節(jié)介紹了 GPU 結(jié)構(gòu)及 GPU 的線程網(wǎng)絡(luò)的基本概念。GPU 是通過 PCI-Express（PCIe）總線連接到主機(jī)系統(tǒng)的外圍設(shè)備。該設(shè)備包括GPU處理器和板載顯存模塊。同時(shí) GPU 還包含與圖像處理相關(guān)的其他部件，因本文算法未涉及到圖像處理，故不進(jìn)行介紹。

【參考文獻(xiàn)】：
期刊論文
[1]CUDA-TP:基于GPU的自頂向下完整蛋白質(zhì)鑒定并行算法[J]. 段瓊,田博,陳征,王潔,何增有.  計(jì)算機(jī)研究與發(fā)展. 2018(07)
[2]加強(qiáng)學(xué)風(fēng)建設(shè) ?防治學(xué)術(shù)腐敗[J]. 郭其云,姜建華.  科研管理. 2016(S1)
[3]GPU通用計(jì)算及其在計(jì)算智能領(lǐng)域的應(yīng)用[J]. 丁科,譚營.  智能系統(tǒng)學(xué)報(bào). 2015(01)
[4]用戶搜索意圖視角下的Web網(wǎng)頁動(dòng)態(tài)泛化研究[J]. 王亞輝.  信息通信. 2014(12)
[5]大數(shù)據(jù)環(huán)境下并行計(jì)算模型的研究進(jìn)展[J]. 潘巍,李戰(zhàn)懷.  華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版). 2014(05)
[6]云服務(wù)平臺(tái)負(fù)載均衡器的網(wǎng)絡(luò)設(shè)計(jì)與實(shí)踐[J]. 夏斌,杜守國.  計(jì)算機(jī)應(yīng)用與軟件. 2014(08)
[7]運(yùn)用學(xué)術(shù)不端文獻(xiàn)檢測系統(tǒng)檢測醫(yī)學(xué)論文存在的問題及對策[J]. 楊晨晨.  編輯學(xué)報(bào). 2014(01)

碩士論文
[1]基于大數(shù)據(jù)平臺(tái)的用戶搜索日志分析和研究[D]. 梁烜彰.華南理工大學(xué) 2018
[2]基于聚類的多層關(guān)聯(lián)規(guī)則挖掘算法研究與改進(jìn)[D]. 何晴.上海師范大學(xué) 2017



本文編號(hào)：3334904