[發(fā)明專利]基于神經(jīng)網(wǎng)絡(luò)的命名數(shù)據(jù)網(wǎng)內(nèi)容存儲池數(shù)據(jù)插入方法

有效

• 申請?zhí)枺?/td>: 201910260772.1
• 申請日: 2019-04-02
• 公開（公告）號: CN110196938B
• 公開（公告）日: 2022-03-01
• 發(fā)明（設(shè)計）人: 周美麗;李卓;劉開華
• 申請（專利權(quán)）人: 天津大學(xué)
• 主分類號: G06F16/953
• 分類號: G06F16/953;G06F12/121;G06F16/957;G06N3/04;G06N3/08;G06F16/951
• 代理公司: 天津市北洋有限責(zé)任專利代理事務(wù)所 12201
• 代理人: 程毓英

1.一種基于神經(jīng)網(wǎng)絡(luò)的命名數(shù)據(jù)網(wǎng)內(nèi)容存儲池數(shù)據(jù)插入方法，所采用的存儲池包括：一個片內(nèi)存儲單元和一個片外存儲單元，所述片內(nèi)存儲單元使用高速存儲器，片內(nèi)部署一個神經(jīng)網(wǎng)絡(luò)模型以實現(xiàn)對數(shù)據(jù)名稱的均勻映射，部署一個改進型位圖（D-bitmap）實現(xiàn)將包含相同名稱前綴的數(shù)據(jù)包映射到同一桶（bucket）中；片外存儲單元使用低速存儲器，其上部署多個與改進型位圖的動態(tài)索引單元的槽（slot）對應(yīng)的動態(tài)存儲器，來存儲每個名稱前綴的跳表信息，用于指導(dǎo)相同名稱前綴Data包在雙向跳表中的下一次查找，以提高數(shù)據(jù)檢索速度；另部署一個雙向跳表結(jié)構(gòu)，以存放數(shù)據(jù)包在學(xué)習(xí)位圖內(nèi)容存儲池中的存儲位置信息，且每個雙向跳表節(jié)點中存有先入先出隊列FIFO單指針和最近最少使用LRU雙指針；

神經(jīng)網(wǎng)絡(luò)模型以實現(xiàn)對數(shù)據(jù)名稱的均勻映射過程如下：

首先，神經(jīng)網(wǎng)絡(luò)采集樣本進行訓(xùn)練，與命名數(shù)據(jù)網(wǎng)名稱數(shù)據(jù)格式類似的大量統(tǒng)一資源定位符URL作為樣本數(shù)據(jù)；其次，計算樣本數(shù)據(jù)的累積分布函數(shù)F(x)值作為標(biāo)簽；然后，訓(xùn)練反向傳播神經(jīng)網(wǎng)絡(luò)，學(xué)習(xí)出能反映索引數(shù)據(jù)分布情況的神經(jīng)網(wǎng)絡(luò)模型，最后，將數(shù)據(jù)名稱的名稱字符串作為輸入，輸入訓(xùn)練出神經(jīng)網(wǎng)絡(luò)模型，得到一個0~1之間的實數(shù)值，該數(shù)值乘以改進型位圖的槽總數(shù)，得到映射標(biāo)號，即實現(xiàn)對數(shù)據(jù)名稱的均勻映射；

雙向跳表數(shù)據(jù)結(jié)構(gòu)設(shè)計如下：

雙向跳表采用多層結(jié)構(gòu)，且每層由一條雙向鏈表構(gòu)成，其跳表節(jié)點按照名稱前綴的ID號增序排列；跳表節(jié)點間用FIFO單指針和LRU雙指針相連，每個節(jié)點中存儲有ID、指向前向節(jié)點指針（prev）和后向節(jié)點的指針（next）信息；

動態(tài)存儲器數(shù)據(jù)結(jié)構(gòu)設(shè)計如下：

動態(tài)存儲器中記錄的內(nèi)容有：名稱前綴、前向節(jié)點(prev_nodes)、前向節(jié)點地址(next_node_addr)、后向節(jié)點(next_nodes)、后向節(jié)點地址(next_node_addr)和當(dāng)前節(jié)點(recent_node)；其中名稱前綴是從數(shù)據(jù)包名稱 名稱前綴,ID中提取出來的；前向節(jié)點和后向節(jié)點是某個節(jié)點在查找時轉(zhuǎn)折的關(guān)鍵節(jié)點對，前向節(jié)點地址和后向節(jié)點地址為節(jié)點地址；當(dāng)前節(jié)點為最近剛查找的節(jié)點；

在所述存儲池中選擇最優(yōu)雙向跳表查找節(jié)點并確定數(shù)據(jù)查找方向過程如下：

利用動態(tài)存儲器中的節(jié)點信息:名稱前綴、前向節(jié)點、前向節(jié)點地址、后向節(jié)點、后向節(jié)點地址和當(dāng)前節(jié)點，選擇最優(yōu)雙向跳表查找節(jié)點并確定查找方向過程如下：

對于有相同名稱前綴的數(shù)據(jù)j，首先比較j的ID和當(dāng)前節(jié)點的ID大小，如果ID當(dāng)前節(jié)點的ID，則從前向節(jié)點中依據(jù)ID號選擇與數(shù)據(jù)j最近的折返節(jié)點作為最佳開始查找節(jié)點；如果ID當(dāng)前節(jié)點的ID，則從后向節(jié)點中選取依據(jù)ID號選擇與數(shù)據(jù)j最近的折返節(jié)點作為最佳開始查找節(jié)點；若選擇的最佳開始節(jié)點的ID小于j的ID，則從最佳開始節(jié)點向后查找，否則，從最佳開始節(jié)點向前查找；并且在數(shù)據(jù)查找過程中，及時更新以上記錄的節(jié)點信息；

在所述存儲池中插入Data包，每插入一個Data包的步驟如下：

步驟1：輸入Data包名稱前綴和ID:輸入Data包的名稱前綴和ID到學(xué)習(xí)位圖內(nèi)容存儲池存儲結(jié)構(gòu)中；

步驟2: 精確名稱匹配：在學(xué)習(xí)位圖中對該名稱前綴直接進行映射操作；

步驟3：計算映射標(biāo)號：該名稱前綴經(jīng)神經(jīng)網(wǎng)絡(luò)運算得到一個0~1之間的索引映射值，該值乘改進型位圖的槽總數(shù)，得出該Data包映射到改進型位圖上的映射標(biāo)號；

步驟4：計算基地址和偏移地址：由映射標(biāo)號除以每個桶的槽總量取整得到該名稱前綴所在的桶序號即為基地址, 名稱前綴進入該桶的順序號為該名稱前綴的偏移地址；

步驟5：判斷改進型位圖中是否存在該名稱前綴：若偏移地址所指向的槽中值不為0，則證明改進型位圖中存在該名稱前綴，執(zhí)行步驟6，否則，證明不存在該名稱前綴，執(zhí)行步驟10；

步驟6：訪問動態(tài)存儲器：由該名稱前綴經(jīng)學(xué)習(xí)位圖訓(xùn)練映射后得到的基地址和偏移地址來訪問動態(tài)存儲器；

步驟7：在雙向跳表中查找Data包:選擇最優(yōu)雙向跳表查找節(jié)點并確定查找方向，在雙向跳表中查找Data包；

7-1：輸入數(shù)據(jù)x的名稱前綴和ID:將數(shù)據(jù)x的名稱前綴和ID號輸入到雙向跳表，此時數(shù)據(jù)x的ID記為id1，且假設(shè)id1是第一次在該名稱前綴所對應(yīng)的雙向跳表結(jié)構(gòu)中進行查找；

7-2：頭結(jié)點查找：按照傳統(tǒng)跳表的查找方式，從雙向跳表跳表中的頭節(jié)點最高層開始向后查找，并將查找路徑節(jié)點信息記錄與動態(tài)存儲器中，并繼續(xù)步驟8；

7-3：輸入數(shù)據(jù)y的名稱前綴和ID ：將與數(shù)據(jù)x有相同前綴的數(shù)據(jù)y的名稱前綴名稱前綴和ID號輸入到雙向跳表輸入，并提取數(shù)據(jù)y的ID號記為id2，假設(shè)輸入的y不是第一次在該名稱前綴所對應(yīng)的雙向跳表結(jié)構(gòu)中進行查找；

7-4：選擇最佳開始查找節(jié)點及查找方向：如果id1大于id2，則從記錄在動態(tài)存儲器中前折返節(jié)點中選擇ID值相差最小的節(jié)點作為最佳節(jié)點，否則，從后折返節(jié)點中選擇ID值相差最小的節(jié)點作為最佳節(jié)點；

7-5：查找雙向跳表：從最佳開始查找節(jié)點按照查找方向進行查找，同時更新動態(tài)存儲器中記錄的折返節(jié)點信息；

步驟8：判斷雙向跳表中是否存在該Data包：在雙向跳表中查找與ID號對應(yīng)的Data包，若未找到ID相同的節(jié)點，則說明不存在該Data包，則執(zhí)行步驟9，否則，執(zhí)行步驟11；

步驟9：插入雙向跳表：按照ID號增序?qū)⒃揇ata包插入雙向跳表，并將名稱前綴記錄與動態(tài)存儲器中，并繼續(xù)執(zhí)行步驟11；

步驟10：創(chuàng)建雙向跳表：對該名稱前綴新建一個雙向跳表，將該數(shù)據(jù)插入跳表中，并將名稱前綴記錄與動態(tài)存儲器中，并繼續(xù)執(zhí)行步驟11；

步驟11：Data包在學(xué)習(xí)位圖內(nèi)容存儲池結(jié)構(gòu)中的插入結(jié)束；

在所述存儲池中雙向查找名稱數(shù)據(jù)，每查找一次名稱數(shù)據(jù)的步驟如下：

步驟1：輸入數(shù)據(jù)x的名稱前綴和ID:將數(shù)據(jù)x的名稱前綴和ID號輸入到雙向跳表，此時數(shù)據(jù)x的ID記為id1，且假設(shè)id1是第一次在該名稱前綴所對應(yīng)的雙向跳表結(jié)構(gòu)中進行查找；

步驟2：頭結(jié)點查找：按照傳統(tǒng)跳表的查找方式，從雙向跳表跳表中的頭節(jié)點最高層查找直至找到id1節(jié)點，并返回該數(shù)據(jù)x的實際存儲地址；

步驟3：記錄折返節(jié)點信息：將id1查找過程中每層跳表的前折返節(jié)點和后折返節(jié)點信息全部記錄于所屬該名稱前綴的動態(tài)存儲器中；

步驟4：輸入數(shù)據(jù)y的名稱前綴和ID ：將與數(shù)據(jù)x有相同前綴的數(shù)據(jù)y的名稱前綴名稱前綴和ID號輸入到雙向跳表輸入，并提取數(shù)據(jù)y的ID號記為id2；

步驟5：判斷ID是否相等：若id1=id2，證明數(shù)據(jù)y與數(shù)據(jù)x相等，則執(zhí)行步驟10，否則執(zhí)行步驟6；

步驟6：選擇最佳開始查找節(jié)點及查找方向：如果id1大于id2，則從記錄在動態(tài)存儲器中前折返節(jié)點中選擇ID值相差最小的節(jié)點作為最佳節(jié)點，否則，從后折返節(jié)點中選擇ID值相差最小的節(jié)點作為最佳節(jié)點；

步驟7：查找雙向跳表：從最佳開始查找節(jié)點按照查找方向進行查找，同時更新動態(tài)存儲器中記錄的折返節(jié)點信息；

步驟8：判斷是否存在該Data包：若雙向跳表中存在ID相等的節(jié)點，則證明存在該Data包，執(zhí)行步驟9，否則，證明不存在該Data包，執(zhí)行步驟10；

步驟9：輸出實際存儲地址：返回該Data包的實際內(nèi)容的存儲地址，繼續(xù)執(zhí)行步驟11；

步驟10：輸出不存在該Data包：輸出不存在該Data包，并繼續(xù)執(zhí)行步驟11；

步驟11：數(shù)據(jù)名稱在雙向跳表結(jié)構(gòu)中的查找結(jié)束。