基于学习的重量级命中者和流量频率在流中的估计

Jun, 2024

基于学习的重量级命中者和流量频率在流中的估计

Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams

Rana Shahout, Michael Mitzenmacher

TL;DR通过使用基于竞争计数的算法，我们提出了一种称为 LSS 的学习算法，用于识别重要对象、top k 以及流量频率的估计，该算法充分利用了众所周知的 Space Saving 算法，并提供了理论洞察以及基于综合和真实世界数据集的实验结果，验证了 LSS 在提高 Space Saving 的准确性和效率方面的能力。

Abstract

identifying heavy hitters and estimating the frequencies of flows are fundamental tasks in various network domains. Existing approaches to this challenge can broadly be categorized into two groups, hashing-based

identifying heavy hitters frequency estimation network domains machine learning space saving algorithm

发现论文，激发创造

改进的频率估计算法（带有或不带有预测）

用机器学习技术改进估计频率的算法，特别是使用了重要元素预测的算法，在一些参数范围内以及加入重要元素预测后，理论上超越了之前算法的性能，并在实验中取得了优于其他方法的表现。

Dec, 2023

通过字级计数进行概率近似推断

该研究提出了一种基于单词级哈希函数的模型计数方法，可以直接利用复杂的 SMT 求解器，为概率推理中的计数问题提供了新思路。

Nov, 2015

DPSW-Sketch: 隐私差分化滑动窗口频率估计的草图框架（技术报告）

在滑动窗口模型中，提出了 DPSW-Sketch，一种基于计数最小化技术的算法，能够满足隐私性要求，并且在子线性时间和空间内近似估计任意项目的频率和重要项，实验结果显示其在效用和隐私权之间取得显著的权衡。

Jun, 2024

高效的分布式局部敏感哈希

本文提出了基于熵局部敏感哈希的分布式分层哈希方案，能够显著减少网络流量，提高实际应用程序的运行效率。

Oct, 2012

使用联邦分析的差分隐私重点检测

通过研究基于前缀树算法的实际启发式方法，我们的工作旨在改进差分隐私重要数据检测算法的性能。我们提出了一种自适应超参数调整算法，以改善算法的性能，并满足计算、通信和隐私约束。通过在 Reddit 数据集上进行广泛实验，我们探究了不同数据选择方案以及在多次算法运行中引入拒绝列表的影响，其中任务是学习最常见的单词。

Jul, 2023

在线哈希

提出了一种在线哈希模型来适应流数据的在线学习，并通过衡量两个数据样本之间在汉明空间中的相似损失来导出结构化哈希模型以被被被优化，该工作对所提出的在线哈希模型累积损失的上界进行了理论分析，并将在线哈希从单一模型扩展到多模型在线哈希，通过在多个大规模数据集上的大量实验验证了所提出的在线哈希模型的竞争效率和效果而言，相比相关的哈希方法。

Apr, 2017

私密联邦频率估计：适应实例的难度

本文基于联邦学习和安全加密协议，提出了一种新的混合化草图算法，可用于对多轮次的频率估计问题进行更准确的处理，并探讨了如何根据实际情况设置草图大小，并验证了算法具有更好的性能。

Jun, 2023

大规模学习的哈希算法

本文提出了一种简单有效的大规模学习方案，结合学习算法（如 SVM 和逻辑回归）的 b 位 minwise 哈希可以自然地集成，大规模问题可以极其高效地解决，并与 Vowpal Wabbit 算法进行比较。

Jun, 2011

具有差分隐私的联邦重要数据发现

通过分布式算法，本文提出了一种隐私保护的方法来发现用户生成数据流中的高频数据，并探讨了隐私和效用之间的平衡，实验证明方法不仅具有良好的效用而且达到了强隐私保障。

Feb, 2019

基于私有设备局部敏感哈希的大规模分布式学习

使用新的哈希函数族，开发第一个在设备上具有私密性、个性化和内存效率高的局部敏感哈希框架，实现了隐私和个性化，能够与其他 LSH 框架相竞争，训练大规模推荐网络。

Jun, 2023