本文選題：CPLSH + 鄰域查詢　； 參考：《太原科技大學(xué)》2017年碩士論文

【摘要】：近年來,進(jìn)化算法逐步成為解決傳統(tǒng)優(yōu)化算法難以克服的復(fù)雜問題的有效手段。但是適應(yīng)值的計(jì)算需要消耗大量的時(shí)間成本,為了減少計(jì)算消耗的時(shí)間,其中一種解決辦法是通過代理模型來估算適應(yīng)值。代理模型一般需要查找個(gè)體的鄰域數(shù)據(jù),通常需要經(jīng)過目標(biāo)數(shù)據(jù)和其他數(shù)據(jù)一一進(jìn)行位置距離比較而得到,時(shí)間復(fù)雜度很大。為了減少代理模型中查找鄰域數(shù)據(jù)所需的時(shí)間,本文利用了局部敏感哈希技術(shù)(LSH)。在基于p-穩(wěn)定分布的局部敏感哈希索引的基礎(chǔ)上進(jìn)行改進(jìn),提出了基于碰撞的p-穩(wěn)定分布的LSH算法(CPLSH),該算法減少了使用哈希函數(shù)的個(gè)數(shù),并選擇碰撞率高的數(shù)據(jù)作為候選集,從而更高效地找到鄰域數(shù)據(jù)。為了驗(yàn)證改進(jìn)后的算法,使用兩個(gè)高維數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),然后與代理模型結(jié)合起來,將其加入到微粒群算法中,利用四種測試函數(shù),通過實(shí)驗(yàn)驗(yàn)證該算法在進(jìn)化算法代理模型中的有效性�；谝陨系难芯�,設(shè)計(jì)實(shí)現(xiàn)了進(jìn)化計(jì)算歷史數(shù)據(jù)的key-value數(shù)據(jù)庫原型系統(tǒng)。除了基本的增刪改查功能外,該系統(tǒng)還增加了鄰域查詢功能,以便有效提高代理模型鄰域查詢的效率。鄰域數(shù)據(jù)的查詢使用基于碰撞的p-穩(wěn)定分布的LSH算法實(shí)現(xiàn)。此外,當(dāng)內(nèi)存數(shù)據(jù)過大時(shí),定期將內(nèi)存數(shù)據(jù)存入磁盤,并構(gòu)建多級(jí)結(jié)構(gòu)區(qū)分熱數(shù)據(jù)和冷數(shù)據(jù),實(shí)現(xiàn)持久化存儲(chǔ)和外存上的高效查詢。
[Abstract]:In recent years, evolutionary algorithm has gradually become an effective means to solve complex problems which are difficult to overcome by traditional optimization algorithms. However, the computation of fitness requires a lot of time cost. In order to reduce the computation time, one of the solutions is to estimate the fitness by proxy model. The agent model usually needs to find the neighborhood data of the individual, and usually needs to compare the location distance between the target data and other data one by one, so the time complexity is very large. In order to reduce the time required to find neighborhood data in the proxy model, a local sensitive hashing technique is used in this paper. Based on the improvement of the locally sensitive hash index based on p-stable distribution, a p-stable LSH algorithm based on collision is proposed. The algorithm reduces the number of hash functions and selects the data with high collision rate as candidate set. Thus, the neighborhood data can be found more efficiently. In order to verify the improved algorithm, two high-dimensional data sets are used to experiment, and then combined with the agent model, the improved algorithm is added to the particle swarm optimization algorithm, and four test functions are used. The effectiveness of the proposed algorithm in the evolutionary agent model is verified by experiments. Based on the above research, a prototype system of key-value database for evolutionary computing history data is designed and implemented. In addition to the basic function of adding, deleting and checking, the system also adds the function of neighborhood query in order to improve the efficiency of neighborhood query of agent model effectively. Neighborhood data query is implemented by LSH algorithm based on collision-stable distribution. In addition, when the memory data is too large, the memory data is stored on disk periodically, and the multi-level structure is constructed to distinguish the hot data from the cold data, so as to realize the efficient query on persistent storage and external memory.
【學(xué)位授予單位】：太原科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP18

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 馬豫星;;Redis數(shù)據(jù)庫特性分析[J];物聯(lián)網(wǎng)技術(shù);2015年03期

2 焦冬冬;徐新國;;一種基于HBase的海量微博數(shù)據(jù)高效存儲(chǔ)方案[J];微型機(jī)與應(yīng)用;2014年11期

3 孫曉燕;陳姍姍;鞏敦衛(wèi);張勇;;基于區(qū)間適應(yīng)值交互式遺傳算法的加權(quán)多輸出高斯過程代理模型[J];自動(dòng)化學(xué)報(bào);2014年02期

4 高毫林;徐旭;李弼程;;近似最近鄰搜索算法——位置敏感哈希[J];信息工程大學(xué)學(xué)報(bào);2013年03期

5 申德榮;于戈;王習(xí)特;聶鐵錚;寇月;;支持大數(shù)據(jù)管理的NoSQL系統(tǒng)研究綜述[J];軟件學(xué)報(bào);2013年08期

6 劉全;王曉燕;傅啟明;張永剛;章曉芳;;雙精英協(xié)同進(jìn)化遺傳算法[J];軟件學(xué)報(bào);2012年04期

7 龍柏;孫廣中;熊焰;陳國良;;一種基于多核機(jī)群架構(gòu)的混合索引結(jié)構(gòu)[J];電子學(xué)報(bào);2011年02期

8 楊衛(wèi)華;;一切為了分布式——2009年Web后端技術(shù)回顧[J];程序員;2010年02期

9 蔡衡;李舟軍;孫健;李洋;;基于LSH的中文文本快速檢索[J];計(jì)算機(jī)科學(xué);2009年08期

10 盧炎生;饒祺;;一種LSH索引的自動(dòng)參數(shù)調(diào)整方法[J];華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年11期

相關(guān)碩士學(xué)位論文 前3條

1 王鵬;圖像檢索中分布式哈希索引技術(shù)研究[D];中國科學(xué)技術(shù)大學(xué);2014年

2 劉英帆;基于局部敏感哈希的近似最近鄰查詢研究[D];西安電子科技大學(xué);2014年

3 凌康;基于位置敏感哈希的相似性搜索技術(shù)研究[D];南京大學(xué);2012年

，

本文編號(hào)：1826814