Jun, 2017

滑动窗口上高效的代表子集选择

PDF
TL;DR提出了一种在数据流上优化代表性子集选择的动态 RSS 方法，即最大化子模函数在具有一般 d - 背包约束 (SMDK) 的滑动窗口上。KnapWindow 框架（KW）利用 KnapStream 算法（KS）为 SMDK 策略中的 “添加仅” 数据流实例，提出 KnapWindowPlus 框架（KW$^{+}$）来改进 KW。实验结果表明，KW 和 KW$^{+}$ 在保持 SMDK 高质量解的同时，比批处理基线减少了两个数量级以上的运行时间。
representative subset selectionsubmodular maximization problemdata streamsd-knapsack constraintskw$^{+}$
发现论文，激发创造
  • 滑动窗口上的次模优化

    本文在数据流的上下文中，提供了一种基于滑动窗口模型的次模优化的近似算法，该算法维护了一个解决方案，考虑的仅是最后 $W$ 个元素，使用空间多项式对元素值的传播速度的对数级别，线性大小的解决方案，并保持高品质的解，实际表现远超理论界限。

    Oct, 2016

  • 从数据流中公平且代表性地选择子集

    本研究旨在探究在数据流中从每个数据组中提取一定数量的代表项目的问题，并提出了一种公正的约束模型和有效的解决方案。该解决方案在最大化覆盖面和个性化推荐方面具有实际应用和较高的性能。

    Oct, 2020

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

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

    Jun, 2024

  • 全息子模流处理：紧密逼近、最小内存和低自适应复杂度

    本文讨论了在 streaming setting 下最大化单调次模函数，并给出了一种新的算法 Sieve-Streaming++ 以及其扩展到多源 streaming setting 的方案，最终将该算法应用于 twitter 和 youtube 视频的多源数据摘要任务中进行效率测试。

    May, 2019

  • 使用滑动窗口选择的快速帕累托优化

    本文介绍了一种滑动窗口加速技术，通过使用这种技术减少算法中的种群规模，达到与之前的方法相同的理论性能保证，同时显著提高解决一系列最大覆盖问题实例和约束设置的结果。

    May, 2023

  • 满足背包约束的敌对鲁棒次模最大化

    该研究提出了针对单个和多个背包约束下的单调次模最大化的首个对抗鲁棒算法，具有可扩展的分布式和流式实现。性能评估结果表明，与现有非鲁棒算法的自然鲁棒化相比，该算法对于大型社交网络图等输入具有最佳的目标结果，并表现出极强的性能，即使与提前给出拆除集合的线下算法相比也是如此。

    May, 2019

  • 非单调 $k$- 次模最大化问题的鲁棒近似算法在背包约束下

    提出了两个确定性近似算法来解决非单调 k - 次模极大化问题，其在查询复杂度仅为 O (nk) 的情况下提供了常数近似比率，比现有算法少使用了 Omega (log n) 数量的查询。

    Sep, 2023

  • 做更少，得更多：带子采样的流式子模最大化

    该论文提出了首个一次遍历的流算法，用于求解子模最大化问题，采用数据采样，能够在各种情况下获得最紧密的逼近保证，同时具有最小的内存占用和对函数评估数量的最低要求，试验表明该算法在进行大规模机器学习问题的子模最大化时能够将其表现提高 50 倍以上

    Feb, 2018

  • 约束 k 次模最大化的在线和流式算法

    本文提出了单遍流式和在线算法的受约束 k - 次模最大化，其中包含基数和背包约束限制，该算法可以提供不错的近似解和高效的解决方案，并在广告分配等应用实例上得到了验证。

    May, 2023

  • 基于分区阈值算法的流式鲁棒次模最大化

    本文研究在流式场景下，求解具有基数限制 k 的单调子模函数最大化问题，提出了一种基于 STAR-T 算法的新型分区结构和指数递减阈值规则，这种算法只需要一次遍历数据，即可保留简短而健壮的总结性概括，还证明了在删除汇总得到的任何 m 个元素后，基于剩余的元素运行的一种简单贪心算法 STAR-T-GREEDY 可获得近似，最后通过两项不同的数据汇总任务证明了 STAR-T 的性能媲美先前的贪心和流式方法。

    Nov, 2017