Dec, 2023

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

PDF
TL;DR用机器学习技术改进估计频率的算法，特别是使用了重要元素预测的算法，在一些参数范围内以及加入重要元素预测后，理论上超越了之前算法的性能，并在实验中取得了优于其他方法的表现。
estimating frequenciessketching approachesmachine learningheavy-hitter oracleperformance
发现论文，激发创造
  • 基于学习的重量级命中者和流量频率在流中的估计

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

    Jun, 2024

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

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

    Jun, 2023

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

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

    Jun, 2024

  • 基于学习的亚线性时间支持估计

    本文提出了一种基于机器学习的辅助估计算法来解决大型数据集中不同元素数量的估计问题，并证明了当预测器正确的逼近因子为常数时，可以显著降低样本复杂度。

    Jun, 2021

  • Count-Min 算法：利用经验误差分布进行最优估计和紧密误差界限

    提供了一些回答，包括新的计数估计器、实用的严格误差界限和最佳的草图调优参数。

    Nov, 2018

  • 学习增强跳表

    通过将机器学习建议整合到跳跃表的设计中，我们改进了传统数据结构设计，并构建了一种能够在几乎两倍内提供最优预期搜索时间的学习增强型跳跃表，即使预估的搜索查询存在误差，该方法依然能够是唯一最优的，而且如果搜索查询符合普遍存在的齐夫分布，那么我们的跳跃表的预期搜索时间只是常数，与项的总数量无关，而传统跳跃表的预期搜索时间则是对数时间。同时，通过实证研究，我们证明了我们的数据结构在合成和真实数据集上均优于传统跳跃表。

    Feb, 2024

  • 本地、私有、高效的简明直方图协议

    本研究给出了关于差分隐私的本地模型下的频率估计的有效协议和匹配准确性下限，研究了能产生数据简明直方图表征的协议，以及在公共硬币模型下的协议。

    Apr, 2015

  • 有关算法子采样的计量经济学视角

    这篇论文研究数据分析中的线性回归和数据素描技术，探讨在样本量有限的情况下如何选择行列子集对数据进行估计和推断，发现虽然算法上的优化子集无法适用于预测和推断，但通过统计学方法可以提供建议的子集大小，并通过实验表明，使用不同的子集来估计结果可以将预测结果效率与使用全样本的方法几乎相同。

    Jul, 2019

  • 自适应采样在加速机器学习算法中的应用

    巨大数据时代需要高效的机器学习算法，本论文表明，通过使用一种特殊的随机替代品，可以在几乎不降低质量的情况下，代替计算密集型子程序。

    Sep, 2023

  • 来自精确采样的流算法

    该研究提出了一种名为 Precision Sampling 的概率性方法来解决一系列数据流算法问题，包括向量构图、重量估算以及求不同范数的估值，同时也能够很好地解决估值的精度问题。

    Nov, 2010