公开(公告)号：CN108304409B

公开(公告)日：2021-11-16

申请号：CN201710024141.0

申请日：2017-01-13

Applicant: 北京大学

Inventor： 杨仝 ,  姜雨萌 ,  李晓明

IPC: G06F16/2455

Abstract: 本发明涉及一种基于进位的Sketch数据结构的数据频度估计方法。该方法包括：1)建立Sketch数据结构，其为由计数器组成的二维数组，其中每一个位置都是一个n位的计数器，在计数器的n位空间中设立标记位和计数位；2)在进行更新操作时，通过哈希函数将数据项映射到所述二维数组中，在映射过程中通过计数位进行计数，并在计数位达到其上限时使用标记位进行进位；3)在进行查询操作时，返回二维数组中每行的查询值中的最小值，作为查询结果。该方法可以采用固定标记位的方式或者多级动态标记位的方式。本发明能够在计数器大小不变的情况下使计数上限显著提升，能够提升计数的准确程度。

公开(公告)号：CN108304409A

公开(公告)日：2018-07-20

申请号：CN201710024141.0

申请日：2017-01-13

Applicant: 北京大学

Inventor： 杨仝 ,  姜雨萌 ,  李晓明

IPC: G06F17/30

Abstract: 本发明涉及一种基于进位的Sketch数据结构的数据频度估计方法。该方法包括：1)建立Sketch数据结构，其为由计数器组成的二维数组，其中每一个位置都是一个n位的计数器，在计数器的n位空间中设立标记位和计数位；2)在进行更新操作时，通过哈希函数将数据项映射到所述二维数组中，在映射过程中通过计数位进行计数，并在计数位达到其上限时使用标记位进行进位；3)在进行查询操作时，返回二维数组中每行的查询值中的最小值，作为查询结果。该方法可以采用固定标记位的方式或者多级动态标记位的方式。本发明能够在计数器大小不变的情况下使计数上限显著提升，能够提升计数的准确程度。