基于块坐标下降算法的优化哈希数据流频率估计  

Frequency estimation of optimized hash data stream based on block coordinate descent algorithm

作　　者：钟章生[1] 袁智勇[1] ZHONG Zhang-sheng;YUAN Zhi-yong(College of Computer Information Engineering,Nanchang Institute of Technology,Nanchang 330013,China)

机构地区：[1]南昌理工学院计算机信息工程学院,江西南昌330013

出　　处：《广西大学学报（自然科学版）》2022年第6期1585-1598,共14页Journal of Guangxi University（Natural Science Edition）

基　　金：国家自然科学基金项目(61663033);江西省教育厅科学技术研究基金项目(GJJ212123);教育部产学合作协同育人基金项目(220500409164010)。

摘　　要：为了不依赖于随机哈希,并且降低计算复杂度,提出了一种基于块坐标下降算法的优化哈希数据流频率估计方法。该方法利用观察到的流媒体数据前缀来接近最佳哈希元素,并压缩目标频率分布。然后引入了一种高效的块坐标下降算法,从而计算最优的哈希方案。提出的方法能够使用动态规划在线性时间内实现精确的求解。最后在合成数据集和搜索查询数据集上对所提出的方法进行了实验评估,结果证明提出的方法能够有效降低计算复杂度,并且保证了较好的估计精度。In order to not rely on random hash and reduce the computational complexity,an optimized hash data stream frequency estimation method based on block coordinate descent algorithm is proposed.This method uses the observed streaming media data prefix to approach the optimal hash element,and compresses the target frequency distribution.Then an efficient block coordinate descent algorithm is introduced to calculate the optimal hash scheme.In addition,the proposed method can use dynamic programming to achieve accurate solution in linear time.Finally,the experimental evaluation of the proposed method is carried out on synthetic data sets and search query data sets.The results show that the proposed method can effectively reduce the computational complexity and ensure better estimation accuracy.

关 键 词：随机哈希 频率估计 流媒体数据 块坐标下降 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]