Sep, 2012

具有线性复杂度的近似两方隐私保护字符串匹配

PDF
TL;DR该研究提出一种系统，可用于保护隐私的字符串匹配。该系统使用确定性逼近而不是精确的距离，适合于云计算，可以缓解由 Goodrich 提出的迭代差分攻击，并与当前的保护隐私的字符串匹配算法进行比较。
发现论文，激发创造
  • 字符串问题和动态时间规整的二次条件下界

    研究了字符串相似性度量的经典算法，探究了其在时间复杂度下限方面的限制，并引入了一个证明相似性度量二次时间难度的框架，进而证明了一个字符串问题在其困难时的时间复杂度下限。

    Feb, 2015

  • PASS-JOIN: 基于划分的相似性连接方法

    本文研究了带有编辑距离约束的字符串相似性联接，提出了一种基于分割的方法 ——Pass-Join，并采用了高效的子串选择和剪枝技术，在实际数据集上显示出比现有算法更高效的结果。

    Nov, 2011

  • 差分隐私聚类：紧密逼近比率

    本论文研究了不同 ially private clustering 任务，为 Euclidean DensestBall、1-Cluster、k-means 和 k-median 等基本聚类问题提供了有效的差分隐私算法，同时只产生小的附加误差，从而实现了与任何非私有算法可以获得的近似比例基本相同的近似比例。这改进了现有的仅实现某些大常数逼近因子的有效算法。我们的结果还暗示了改进的 Sample and Aggregate 隐私框架算法。此外，我们展示了在适度的维数下，可以利用我们的 1-Cluster 算法中使用的工具来获得更快的 ClosestPair 量子算法。

    Aug, 2020

  • 线性查询处理的凸优化在近似差分隐私下的应用

    通过解决凸优化问题，利用 Newton 方法能够找到基于（Ε，δ）差分隐私下的合适策略，以计算数据的相关聚合，从而提高结果准确度。

    Feb, 2016

  • 离散分布身份和接近性的差分隐私测试

    该研究提供了关于差分隐私下 k 个元素分布的标识检测和接近度检验的上下界。他们提出了一般框架以建立隐私统计任务的样本复杂度的下界，同时通过构建精心选择的先验概率来证明隐私算法的下界。

    Jul, 2017

  • 私有学习和加噪：纯差分隐私与近似差分隐私

    该研究通过将真正的差分隐私和近似（ε，Δ）- 差分隐私应用于优化问题中，研究比较了私有学习和消毒的样本复杂性，同时构建了用于高维中的点函数，阈值函数和轴对齐矩形的私有学习器以及标签私有学习，证明了 VC 维完全刻画了学习带标签隐私的样本复杂性。

    Jul, 2014

  • 基于字符串核的序列分类的高效近似算法

    本文中，我们提出了一种新的技术，能够高效准确地估计序列之间的相似度得分，从而增加了序列分类方法在音频、图像和文本序列中的应用广度，并且取得了良好的理论和实验表现。

    Dec, 2017

  • 在精确和近似差分隐私下优化批线性查询

    本文提出了第一个用于回答批量线性查询的实用差分隐私技术，即低秩机制 (LRM)，它适用于确切和近似差分隐私定义，并提供对 LRM 的实用性保证，同时提供如何根据用户的实用预期设置隐私参数的指导。与差分隐私下的最新查询处理解决方案相比，这种方法在真实数据上的大规模实验中表现出了更高的准确性。

    Feb, 2015

  • 随机匹配问题的改进近似算法

    本文研究了随机匹配问题，提出一种能够提高精度的探测边的新方法和其在最大化构建匹配的期望收益中的应用，尤其在求解在线偏二分图情况时取得了显著提升。

    May, 2015

  • 差分隐私的几何学：稀疏和近似情况

    通过使用关联的高斯噪声和线性回归步骤，我们基于差分隐私机制的多项式对数组进行了矩阵突触连接和遗传差异，从而在线性查询的上下文中研究了准确性和隐私之间的权衡。

    Dec, 2012