【24h】

Fast Private Data Release Algorithms for Sparse Queries

机译:稀疏查询的快速私有数据发布算法

获取原文
获取原文并翻译 | 示例

摘要

We revisit the problem of accurately answering large classes of statistical queries while preserving differential privacy. Previous approaches to this problem have either been very general but have not had run-time polynomial in the size of the database, have applied only to very limited classes of queries, or have relaxed the notion of worst-case error guarantees. In this paper we consider the large class of sparse queries, which take non-zero values on only polynomially many universe elements. We give efficient query release algorithms for this class, in both the interactive and the non-interactive setting. Our algorithms also achieve better accuracy bounds than previous general techniques do when applied to sparse queries: our bounds are independent of the universe size. In fact, even the runtime of our interactive mechanism is independent of the universe size, and so can be implemented in the "infinite universe" model in which no finite universe need be specified by the data curator.
机译:我们将重新讨论在保留差异性隐私的同时准确回答大类统计查询的问题。以前解决此问题的方法要么很通用,但没有数据库大小的运行时多项式,要么仅应用于非常有限的查询类,要么放宽了最坏情况错误保证的概念。在本文中,我们考虑了一大类稀疏查询,它们仅对多项式许多Universe元素采用非零值。在交互式和非交互式设置中,我们都为此类提供了有效的查询释放算法。与应用于稀疏查询的常规技术相比,我们的算法还可以实现更好的精度范围:我们的范围与Universe大小无关。实际上,甚至我们交互机制的运行时也与Universe大小无关,因此可以在“无限Universe”模型中实现,在该模型中,数据管理者无需指定任何有限Universe。

著录项

  • 来源
  • 会议地点 Berkeley CA(US)
  • 作者

    Avrim Blum; Aaron Roth;

  • 作者单位

    Department of Computer Science, Carnegie Mellon University, Pittsburgh PA 15213,Department of Computer and Information Science, University of Pennsylvania, Philadelphia PA 19104. This research was partially supported by an NSF CAREER;

    Department of Computer Science, Carnegie Mellon University, Pittsburgh PA 15213,Department of Computer and Information Science, University of Pennsylvania, Philadelphia PA 19104. This research was partially supported by an NSF CAREER;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号