[發(fā)明專利]一種基于進位的Sketch數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)頻度估計方法

有效

• 申請?zhí)枺?/td>: 201710024141.0
• 申請日: 2017-01-13
• 公開（公告）號: CN108304409B
• 公開（公告）日: 2021-11-16
• 發(fā)明（設(shè)計）人: 楊仝;姜雨萌;李曉明
• 申請（專利權(quán)）人: 北京大學(xué)
• 主分類號: G06F16/2455
• 分類號: G06F16/2455
• 代理公司: 北京君尚知識產(chǎn)權(quán)代理有限公司 11200
• 代理人: 邱曉鋒

本發(fā)明涉及一種基于進位的Sketch數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)頻度估計方法。該方法包括：1)建立Sketch數(shù)據(jù)結(jié)構(gòu)，其為由計數(shù)器組成的二維數(shù)組，其中每一個位置都是一個n位的計數(shù)器，在計數(shù)器的n位空間中設(shè)立標記位和計數(shù)位；2)在進行更新操作時，通過哈希函數(shù)將數(shù)據(jù)項映射到所述二維數(shù)組中，在映射過程中通過計數(shù)位進行計數(shù)，并在計數(shù)位達到其上限時使用標記位進行進位；3)在進行查詢操作時，返回二維數(shù)組中每行的查詢值中的最小值，作為查詢結(jié)果。該方法可以采用固定標記位的方式或者多級動態(tài)標記位的方式。本發(fā)明能夠在計數(shù)器大小不變的情況下使計數(shù)上限顯著提升，能夠提升計數(shù)的準確程度。

技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)安全、金融分析、機器學(xué)習(xí)、自然語言處理等多個重要領(lǐng)域，具體為一種基于進位的Sketch數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)頻度估計方法。

背景技術(shù)

目前，Count-Min Sketch(Graham Cormode,S.Muthukrishnan.An Improved DataStream Summary:The Count-Min Sketch and Its Applications[M])，即計數(shù)-最小略圖，是使用最多，性能最好，最普適于各種數(shù)據(jù)的一種Sketch。它相對輕巧，實時計數(shù)簡單快速，可擴展性較強，存儲和計算復(fù)雜度都很低。

然而，作為一個輕量級甚至被GPU所使用的數(shù)據(jù)結(jié)構(gòu)(Y.Wang,Y.Zu,and etal.Wire speed name lookup:A gpu-based approach.In Proc.USENIX NSDI,pages 199–212,2013.)，Count-Min Sketch在性能上仍有較大局限，例如其查詢準確率對使用空間的大小較為敏感，空間大小的限制會很大程度上制約其準確率。同時其數(shù)據(jù)結(jié)構(gòu)設(shè)計較為簡單，導(dǎo)致數(shù)據(jù)量存儲上限十分有限。

發(fā)明內(nèi)容

為了克服現(xiàn)有的Count-Min Sketch計數(shù)方式原始的不足,本發(fā)明提供一種提升一定比特所能表達的值域上限的計數(shù)方法。

本發(fā)明采用的技術(shù)方案如下：

一種基于進位的Sketch數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)頻度估計方法，包括以下步驟：

1)建立Sketch數(shù)據(jù)結(jié)構(gòu)，其為由計數(shù)器組成的二維數(shù)組，其中每一個位置都是一個n位的計數(shù)器，在計數(shù)器的n位空間中設(shè)立標記位和計數(shù)位；

2)在進行更新操作時，通過哈希函數(shù)將數(shù)據(jù)項映射到所述二維數(shù)組中，在映射過程中通過計數(shù)位進行計數(shù)，并在計數(shù)位達到其上限時使用標記位進行進位；

3)在進行查詢操作時，返回二維數(shù)組中每行的查詢值中的最小值，作為查詢結(jié)果。

進一步地，步驟1)采用固定標記位的方式，即將計數(shù)器的n位空間中高x位作為標記位，剩下的n-x位作為計數(shù)位。

或者，步驟1)采用多級動態(tài)標記位的方式，標記位的個數(shù)和計數(shù)位的個數(shù)根據(jù)存儲的數(shù)值進行動態(tài)調(diào)整。

一種查詢串頻次統(tǒng)計方法，包括以下步驟：

1)使用權(quán)利要求1所述Sketch數(shù)據(jù)結(jié)構(gòu)記錄用戶每次檢索使用的檢索串的出現(xiàn)次數(shù)；

2)對于每個查詢串，根據(jù)所述Sketch數(shù)據(jù)結(jié)構(gòu)得到其出現(xiàn)次數(shù)的查詢值，進而得到出現(xiàn)次數(shù)最大的k個查詢串。

進一步地，步驟2)對某個查詢串獲取的查詢值如果不足以排進出現(xiàn)次數(shù)最大的k個查詢串之中，則無需去片外的哈希表中獲取其真實值。

本發(fā)明的有益效果是：