关键词:
k-匿名
数据质量
泛化树
准标识符最佳值
NP-完全
节点链枚举树
摘要:
k-匿名方法是视图发布条件下防止数据隐私泄露的一种重要方法,准标识符值是影响k-匿名表隐私保护程度和数据质量的关键因素,如何在给定各个准标识符属性泛化树的情况下求解准标识符最佳值,对匿名表在满足隐私保护要求的同时提高实用性有重要的意义。本文详细分析了视图发布安全问题的研究现状,提出了k-匿名隐私保护模型中的准标识符最佳值求解问题,并对准标识符最佳值的求解问题进行了深入的研究。
首先,给出了准标识符最佳值的概念,为了进一步提高匿名表的实用性,在信息需求者提供准标识符属性泛化树的条件下,提出了准标识符最佳值的求解问题,并证明了准标识符最佳值的求解问题是NP-完全问题。
其次,基于准标识符最佳值的求解问题,提出了求解准标识符最佳值的贪婪算法,并综合考虑匿名表的数据质量,在保证匿名表不泄露隐私的同时,近似求解准标识符最佳值。
再次,结合基于实用性要求的信息损失度量公式,提出了基于节点链枚举树的准标识符最佳值求解方法,该方法通过动态构建节点链枚举树来搜索最佳节点链,综合考虑多种减少搜索空间策略,提高了搜索效率,并由最佳节点链求解准标识符最佳值,并在此基础上提出了基于节点链枚举树的准标识符最佳值求解算法。
最后,对上述算法进行了实验验证,给出实验结果,并对实验结果进行了分析和比较,证明了算法的可行性及有效性。