基于块坐标下降算法的优化哈希数据流频率估计_钟章生.pdf

第 卷 第期 年 月广西大学学报（自然科学版）（）收稿日期：；修订日期：基金资助：国家自然科学基金项目（）；江西省教育厅科学技术研究基金项目（）；教育部产学合作协同育人基金项目（）。通讯作者：钟章生（），男，江西赣州人，南昌理工学院副教授；：。引文格式：钟章生，袁智勇基于块坐标下降算法的优化哈希数据流频率估计广西大学学报（自然科学版），（）：基于块坐标下降算法的优化哈希数据流频率估计钟章生，袁智勇（南昌理工学院 计算机信息工程学院，江西 南昌 ）摘要：为了不依赖于随机哈希，并且降低计算复杂度，提出了一种基于块坐标下降算法的优化哈希数据流频率估计方法。该方法利用观察到的流媒体数据前缀来接近最佳哈希元素，并压缩目标频率分布。然后引入了一种高效的块坐标下降算法，从而计算最优的哈希方案。提出的方法能够使用动态规划在线性时间内实现精确的求解。最后在合成数据集和搜索查询数据集上对所提出的方法进行了实验评估，结果证明提出的方法能够有效降低计算复杂度，并且保证了较好的估计精度。关键词：随机哈希；频率估计；流媒体数据；块坐标下降中国分类号：文献标识码：文章编号：（），（，）：，：；广西大学学报（自然科学版）第 卷引言流媒体模型在搜索查询监控、网络流量监控等应用中发挥了极其重要的作用，在这些应用中最基本的问题之一是频率估计，即在输入流中，估计每个元素的发生次数。数据流通常具有大容量的特征，因此，如何实现大型流媒体数据的频率估计成为了研究的热点问题。是处理流媒体数据的最强大工具之一，它是一种数据结构，可以表示为输入的线性变换。等提出一种基于 的可动态调整的 算法：。该算法根据对流数据规模的估计，调整多层 层级结构的内存分配，保证数据的存储位置在内存调整前后是一致的。等基于二项式分布和中心极限定理，结合 处理大数据流的事件频率表。等提出了一种基于桶 的用于覆盖聚类和多样性最大化问题的空间高效滑动窗口算法，有效实现了流计算中的频率估计。虽然上述方法取得了一定效果，但是上述频率估计任务的估计精度极大地依赖于随机哈希，导致估计精度稳定性较低，可行性较差。为了进一步提升估计精度，有大量文献将深度学习算法引入到流媒体数据频率估计中。等提出了一种基于深度卷积神经网络的流媒体频率估计算法，通过卷积神经网络（，）处理元素的列集，从而提升算法的适用性。甘元艺提出了一个面向流的大数据应用的延迟和资源感知调度框架（），旨在优化延迟和吞吐量，并且利用深度网络对系统指标进行了全面评估。等提出了一种基于强化学习和神经网络学习的调度算法流式数据排序，用于在单处理器上处理受有限存储大小和排序顺序正确性约束的流式数据。赵鹏等使用可解释的机器学习方法学习连续和混合整数凸优化问题最优解背后的策略，作为其关键参数的函数，对大型视频流数据实现频率估计。虽然上述方法利用深度学习的强非线性映射能力极大地提升了频率估计的准确性；但是由于流媒体数据规模较大，加上深度学习的训练要求较高，因此导致计算成本较高，很难实现实时估计功能。为了解决上述个问题，本文提出了一种基于块坐标下降算法的优化哈希数据流频率估计，并且通过实验结果证明了所提出方法的有效性。相关理论 随机 方法用索引表示变量，索引和表示变量标号，索引表示存储桶。为便于标记，根据上下文使用符号或表示元素；以此类推，使用这种方法中的任何一种对频率进行索引。以元素的有序集合（，）的形式给出输入数据，其中，是输入元素的集合。每种元素的形式为（，），其中是一组与相关的特性。本文旨在的末尾给定一个元素，估计值的输出频率为（），（）即该元素在中出现的次数；本文中，表示事件的指示函数。假设和都是较大的，因此希望在比 ，小得多的空间中实现准确估计。在额外的假设下，即已经观察到的输入流的前缀（，），其中。解决此问题的标准方法是流行的 （），一种基于随机哈希的概率数据结构，用作的频率表。简言之，通过随机线性哈希函数 （）随机哈希每个元素到大小为 ，的数组中的桶；每当元素出现在中时，相应的计数器 （）就会递增。由于，多个元素被映射到同一个桶，因此 （）将高估。实际上，多个阵列，第期钟章生，等：基于块坐标下降算法的优化哈希数据流频率估计保持不变，的最终估计值为其中 （）是对应于第个级别的哈希函数。通过多次重复估计过程并取估计频率中的最小值，所得估计器的精度可以得到提高。为其估计的准确性提供概率保证，即，对于每个、概率为、，其中和。总的来说，由个桶组成。基于学习的方法为了利用观察到的流的前缀，等 对经典算法进行如下扩充。注意到影响估计误差最大的元素是重复击中元素，该文献提出训练分类器：，预测元素（，）是否将成为 。然后，将 唯一的桶分配给识别为重打击者的元素，并使用标准 随机分配剩余的 个桶，称该算法为学习计数最小 （）。另外，分配给 的每一个 唯一桶都应保持相关元素的频率和元素名称。如上文所述，这可以通过使用具有开放寻址的哈希来实现，由此它足以将哈希的 存储为 位，以确保不会与概率发生冲突。与每个计数器的位数相当，唯一存储桶的空间是普通存储桶的倍。从理论和经验上看，学习增强算法都优于传统的完全随机算法，然而，该方法仍然是启发式的，不能保证获得最佳性能。基于块坐标下降算法的优化哈希数据流频率估计本文两阶段方法的工作原理如下。在第一阶段，流前缀中出现的元素根据其观察到的频率以最佳方式分配给桶，从而使频率估计误差最小化，同时，将相似的元素映射到相同的桶。与基于的方法相反，在所提出的方法中，元素频率的估计是映射到同一桶的所有元素的频率的平均值，因此，本文目标是将“相似”元素分配给同一个桶。在第二阶段，一旦对前缀中出现的元素进行了优化分配，将根据元素的特征训练一个分类器，将元素映射到桶。通过这种方法，能够提供前缀中未出现的不可见元素的估计值，因此不会记录它们的频率。提出的哈希方案包括一个哈希表，将前缀中出现的元素 映射到桶和学习的分类器。此外，对于每个桶，需要保持其中映射的所有元素的频率之和。在流处理期间，一旦估计器准备就绪，每当前缀中出现的元素重新出现时，增加元素映射到的桶的计数器，即聚合频率。最后，为了实现任何给定元素的计数查询，只需通过哈希表或分类器输出映射元素的桶的当前平均频率。学习最佳哈希方案设（，）为 观 测 流 前 缀。用表 示 元 素在中 的 经 验 频 率，即（），通过（）观察后的整个频率分布。此外，：是在中出现的所有不同元素的集合，并且。引入二进制变量，其中是可用桶的总数，定义为，如果将的元素映射到容器，其他。的每一行都可以作为将元素映射到其中一个存储桶的一个二进制哈希代码，其中，。在流的末尾，固定变量 的值，元素 的频率的最终估计是 （）。相应的绝对估计误差为，目标是选择变量，使观测流前缀中的绝对误差最小化。可以选择的另一个目标是绝对误差的预期大小，其中假设观测元素的概率等于其在观测流前缀中的经验概率，即。然而，这种方法将对最经常发生的因素产生重大影响。由于希望本文目标函数能够对所有元素上的错误进行统一且独立于元素的观测频率的惩广西大学学报（自然科学版）第 卷罚，因此坚持实现前一个目标，并选择变量，以解决优化公式。在本文提出的目标函数中加入了一个附加项，以在计算元素到桶的最佳映射时考虑与每个元素相关的特征。对于，有 ，（），。（）参数，控制哈希方案之间的权衡，这些哈希方案映射到相同的桶元素，桶元素在前缀（）中观察到的频率相似，以及对元素的特征相似性（）施加更大权重的哈希方案，因此，将目标中的第一项称为估计误差，将第二项称为相似性误差。式（）是一个非线性二元优化问题，很难解决，因此，下一步将提出不同的方法，用于在不同制度下求解最优解或接近最优的解。混合整数线性格式式（）等价于下面的混合整数线性优化问题：，（），（），。（）证明过程与文献 中定理证明过程类似。问题（）由（）个变量和约束项组成。在本文所考虑的应用中，求解混合整数线性优化问题的计算量仍然是巨大的。为了解决该问题，本文提出了一种块坐标下降算法。高效块坐标下降算法通过利用问题（）结构，提出了高效块坐标下降算法，该算法既可以启发式地解决问题（），也可以用于计算问题（）。关于算法的初始化过程，随机分配元素的值，或者，可以根据观察到的频率对中的元素进行排序，并将第个 元素分配给第个桶，将下一个 分配给第个桶。依此类推，或者可以使用重击启发法。在实现过程中，为每个桶保持其中映射的元素集、基数、平均频率，以及相关的估计误差和相似性误差（，）。在高效块坐标下降算法更新所有参数后，只需更新上述变量，而无需从头开始重新计算，因此，可以直接评估与元素到桶的任何特定映射相关的第期钟章生，等：基于块坐标下降算法的优化哈希数据流频率估计目标函数值。在每次迭代中，高效块坐标下降算法按顺序和随机顺序检查个变量，的所有个块，每个块包含特定元素到任何桶的所有可能的映射。对于每个元素，选择较多映射值，使总体估计误差最小化。为此，将元素从当前存储桶中移除，并计算与每个存储桶相关的估计误差，将元素分配到存储桶，然后将元素从存储桶移除，将元素分配到存储桶，使所有误差项的总和最小化。当改进后的估计误差可以忽略时，算法终止；如果希望更快地获得中间解决方案，可以将终止标准设置为用户指定的最大迭代次数。经验表明，高效块坐标下降算法经过几十次迭代后收敛到局部最优，并得到性能较优的解。由于该算法不能保证收敛到全局最优解，因此该过程可以设置多组初始值，重复多次实验。可以有效地实现高效块坐标下降算法，使每次迭代的复杂度为（）。这是意料之中的，因为对于每个桶，需要计算映射到其中的所有元素对之间的相似性错误，该过程的计算复杂度为（）。动态规划算法当的特殊情况下，即在计算最优哈希方案时，不考虑特征，可以得到以下公式：，。（）式（）是一个一维中值聚类问题，根据文献 ，提出了一个复杂度为（）的动态规划算法解决问题（）的最优性。在最优量化背景下，对问题（）提出了一种更有效的求解方法；使用动态规划结合矩阵搜索技术，问题（）的最优性的计算复杂度为（）。频率估计 前缀中元素的频率估计一旦计算了最优赋值，对于每个元素，就得到了一个哈希码（），因此，对于元素，由索引，简单地估计其频率为。：表示根据学习到的哈希码将前缀中的元素映射到桶的函数。基于相似性的不可见元素频率估计能够为前缀中未出现的元素生成频率估计值，即，制定了一个多分类问题，根据元素的特征将元素映射到桶。搜索到一个函数：，训练集由所有数据点组成，即前缀中出现的元素的所有特征哈希代码元组。这样的分类器可以令基于“看起来”相似的元素的平均频率来估计不可见元素的频率，元素（，）的估计值为：（）：（）。自适应计数扩展上文描述了一种静态方法。学习流前缀中出现的元素的最佳哈希方案，然后只跟踪它们的频率，所有参数的估计频率仅基于中元素的频率。下文将描述一种动态方法，它跟踪中元素频率以外的元素频率。在较高的层次上，自适应方法基于对每个桶中不同元素的近似计数。工作步骤如下：学习基于观察到的流前缀的最佳哈希方案，并训练将元素映射到桶的分类器，如上所述。对于每个桶，只记录其中映射的元素数量，而不是存储映射到此桶的元素的。使用分类器来确定任何元素映射到哪个桶。在给定元素和集合 的情况下，针对所有元素或者，进行概率测试，对应于流数据中出现的元素。如果，那么 过滤器（）；如果，那么就不需要（）。广西大学学报（自然科学版）第 卷根据元素初始化 过滤器。一方面，将所有元素初始化为（）；另一方面，可能将元素初始化为（）或（）。对于在处理流前缀之后出现在流中的每个后续元素，将其映射到桶使用经过训练的分类器。然后，使用 过滤器测试是否已经找到。如果（），则增加频率和桶中的元素数，并令（）；如果（），只增加频率。查询任何元素的频率时，不管是否出现在中，都估计，其中是使用分类器映射的桶。过滤器误报的影响是，本文方法将标记流中未出现的可见元素。当该元素出现在流中时，不会增加计数器，该计数器跟踪该元素映射的桶中的元素数量，因此，中元素的估计数量将小于实际数量，故而，自适应计数扩展通常会高估元素的频率。有关合成数据的实验 数据合成在合成实验中使用的数