首页> 外文会议>Algorithms and data structures >On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem
【24h】

On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem

机译:几何和地理概化的逼近性和最小-最大箱体覆盖问题

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

摘要

We study the problem of abstracting a table of data about individuals so that no selection query can identify fewer than k individuals. We show that it is impossible to achieve arbitrarily good polynomial-time approximations for a number of natural variations of the generalization technique, unless P = NP, even when the table has only a single quasi-identifying attribute that represents a geographic or unordered attribute:rn1. Zip-codes: nodes of a planar graph generalized into connected subgraphsrn2. GPS coordinates: points in R~2 generalized into non-overlapping rectanglesrn3. Unordered data: text labels that can be grouped arbitrarily.rnThese hard single-attribute instances of generalization problems contrast with the previously known NP-hard instances, which require the number of attributes to be proportional to the number of individual records (the rows of the table). In addition to impossibility results, we provide approximation algorithms for these difficult single-attribute generalization problems, which, of course, apply to multiple-attribute instances with one that is quasi-identifying. Incidentally, the generalization problem for unordered data can be viewed as a novel type of bin packing problem-min-max bin covering-which may be of independent interest.
机译:我们研究了抽象有关个人的数据表的问题,这样任何选择查询都不能识别出少于k个个人。我们证明,除非P = NP,否则即使表只有一个表示地理属性或无序属性的准标识属性,也无法获得针对泛化技术的许多自然变化的任意良好的多项式时间近似值: rn1。邮政编码:将平面图的节点概括为连接的子图rn2。 GPS坐标:R〜2中的点一般化为非重叠矩形rn3。这些无序数据:可以任意分组的文本标签。这些泛化问题的硬性单属性实例与以前已知的NP硬性实例形成对比,后者要求属性的数量与单个记录的数量成正比(即表)。除了不可能的结果外,我们还为这些困难的单属性泛化问题提供了一种近似算法,这些算法当然适用于具有一个准标识的多属性实例。顺便提一句,无序数据的泛化问题可以看作是一种新型的装箱问题-最小-最大装箱覆盖-这可能是独立引起关注的问题。

著录项

  • 来源
    《Algorithms and data structures》|2009年|P.242-253|共12页
  • 会议地点 Banff(CA);Banff(CA)
  • 作者单位

    Department of Electrical Engineering and Computer Science, Syracuse University, 3-114 Sci-Tech Building. Syracuse, NY 13244;

    Dept. of Computer Science, Univ. of California, Irvine, CA 92697-3435;

    Dept. of Computer Science, Univ. of California, Irvine, CA 92697-3435;

    Dept. of Computer Science, Univ. of California, Irvine, CA 92697-3435;

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

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号