[發(fā)明專利]基于離群值檢測技術(shù)和位圖索引的動態(tài)數(shù)據(jù)庫填充方法

有效

• 申請?zhí)枺?/td>: 202110395631.8
• 申請日: 2021-04-13
• 公開（公告）號: CN113076319B
• 公開（公告）日: 2022-05-06
• 發(fā)明（設(shè)計）人: 杜瑞忠;張玉晴
• 申請（專利權(quán)）人: 河北大學(xué)
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/23;G06F21/62
• 代理公司: 石家莊國域?qū)＠虡?biāo)事務(wù)所有限公司 13112
• 代理人: 胡素梅

1.一種基于離群值檢測技術(shù)和位圖索引的動態(tài)數(shù)據(jù)庫填充方法，其特征是，包括如下步驟：

a、生成填充數(shù)據(jù)庫；

對數(shù)據(jù)庫中關(guān)鍵字按關(guān)鍵字頻率進(jìn)行聚類；關(guān)鍵字頻率指關(guān)鍵字出現(xiàn)在各文件中的頻次，以文件數(shù)來記錄關(guān)鍵字頻率；每個簇中每一關(guān)鍵字按照頻率最大的關(guān)鍵字填充至相同的數(shù)量，具體是：根據(jù)每個關(guān)鍵字需要填充偽文件的數(shù)量隨機生成偽文件進(jìn)行填充，直到所有關(guān)鍵字填充至最大填充計數(shù)為止；由填充的偽文件生成填充數(shù)據(jù)庫，并生成相應(yīng)索引；

步驟a中，生成偽文件的方法如下：將需填充的關(guān)鍵字以及關(guān)鍵字對應(yīng)的需填充的偽文件的數(shù)量一并放入集合G中；從集合G中需填充的關(guān)鍵字中隨機選取τ位關(guān)鍵字進(jìn)行填充以生成偽文件v，其中τ是從范圍[l,u]中隨機選取的，l和u分別是數(shù)據(jù)庫中最小文件大小和最大文件大小；對所生成的偽文件v進(jìn)行離群值檢測，如果偽文件v沒有被識別為離群值，則將所生成的偽文件v加入填充數(shù)據(jù)庫，相應(yīng)地，偽文件v中包含有某一關(guān)鍵字，集合G中與該關(guān)鍵字對應(yīng)的需填充的偽文件的數(shù)量減1；如果偽文件v被識別為離群值，則重新從集合G中需填充的關(guān)鍵字中隨機選取τ位關(guān)鍵字進(jìn)行填充以生成偽文件v，如此循環(huán)，直至集合G中所有關(guān)鍵字對應(yīng)的需填充的偽文件的數(shù)量為0；

b、根據(jù)更新操作動態(tài)調(diào)整填充數(shù)據(jù)庫；

更新操作包括對關(guān)鍵字的添加操作和對關(guān)鍵字的刪除操作；

若更新操作為對關(guān)鍵字的添加操作，則首先判斷添加后的關(guān)鍵字頻率是否最大，如果是，則根據(jù)此關(guān)鍵字頻率對其他關(guān)鍵字進(jìn)行填充；否則對填充數(shù)據(jù)庫中此關(guān)鍵字對應(yīng)的填充偽文件進(jìn)行刪除；

若更新操作為對關(guān)鍵字的刪除操作，則對填充數(shù)據(jù)庫中未填充此關(guān)鍵字的偽文件進(jìn)行填充；

對關(guān)鍵字進(jìn)行填充或?qū)㈥P(guān)鍵字對應(yīng)的偽文件進(jìn)行刪除，均應(yīng)首先進(jìn)行嘗試性更改偽文件，之后對偽文件進(jìn)行離群值檢測，如果偽文件沒有被識別為離群值，則更改相應(yīng)偽文件并更新填充數(shù)據(jù)庫以及對應(yīng)索引；如果偽文件被識別為離群值，則回滾到嘗試性更改前的狀態(tài)，并選擇下一個偽文件進(jìn)行嘗試性更改，再對偽文件進(jìn)行離群值檢測，如此循環(huán)；

c、判斷每個關(guān)鍵字的頻率是否均相同，如果是，則更新操作完成；否則循環(huán)執(zhí)行步驟b。

2.根據(jù)權(quán)利要求1所述的基于離群值檢測技術(shù)和位圖索引的動態(tài)數(shù)據(jù)庫填充方法，其特征是，步驟a中，生成索引的依據(jù)如下：

根據(jù)位圖索引的表示方法與運算規(guī)則：設(shè)數(shù)據(jù)庫中包含n個文件，對于每個關(guān)鍵詞，對應(yīng)一個n位長的比特串，如果關(guān)鍵字存在于文件f_i中，則將比特串的第i位設(shè)為1，否則設(shè)置為0；對于添加或者刪除文件/關(guān)鍵字對，需要生成對應(yīng)比特串并將其加到初始比特串上。

3.根據(jù)權(quán)利要求1所述的基于離群值檢測技術(shù)和位圖索引的動態(tài)數(shù)據(jù)庫填充方法，其特征是，步驟b中，離群值檢測的依據(jù)如下：

對于一個偽文件v，它的k近鄰N(v)首先通過測量每個真實文件點的海明距離d來導(dǎo)出：

N(v)←{r∈D\v|d(v,r)≤k-dist(v)} (1)

其中r為真實文件，D為真實文件的集合，k-dist(v)是偽文件v和它的k近鄰之間的距離，之后，可達(dá)距離計算如下：

reach-dist(v,r)＝max{k-dist(r),d(v,r)} (2)

然后，偽文件v的局部可達(dá)性密度計算如下：

最后，計算離群因子LOF(v)：

其中，lrd(r)為真實文件r的局部可達(dá)性密度；

經(jīng)過計算LOF值來進(jìn)行離群值檢測，如果LOF(v)1，則表明此偽文件沒有被識別為離群值，否則該偽文件被識別為離群值。

4.根據(jù)權(quán)利要求1所述的基于離群值檢測技術(shù)和位圖索引的動態(tài)數(shù)據(jù)庫填充方法，其特征是，在生成偽文件的過程中，為了對所生成的符合條件的偽文件進(jìn)行表示，采用一個m維的位向量，m是關(guān)鍵字空間的大小，若偽文件v中包含某一關(guān)鍵字，則在m維位向量中將與該關(guān)鍵字對應(yīng)的位置設(shè)置為1；否則設(shè)置為0。