DSE精选文章 | Set-Based Adaptive Distributed Diferential Evolution for Anonymity-Driven…【转发】
133
2022-09-15
1
0
0
用微信扫描二维码

https://mp.weixin.qq.com/s/gbMpds_GHENUQQvy0fZSLw

 

DSE精选文章

Set-Based Adaptive Distributed Diferential Evolution for Anonymity-Driven Database Fragmentation

 

Data Science and Engineering (DSE)是由中国计算机学会(CCF)主办,数据库专业委员会承办,施普林格·自然(Springer Nature)集团出版的开放获取(OA)期刊。本篇文章精选自DSE第6卷第4期发文,得到中新赛克赞助文章处理费。

 

文章介绍

数据库碎片可以通过打破属性之间的敏感关联来保护外包数据存储的隐私。数据库碎片算法需要先验知识处理数据库中的敏感关联,因此这些算法的有效性受到先验知识的限制。受匿名技术中匿名度度量的启发,该文提出了一种基于集合的自适应分布式差分进化(S-ADDE)算法,用于解决匿名驱动的数据库碎片问题。S-ADDE中的个体代表数据库分片的解,每个解的匿名度设置为个体的ftness值。S-ADDE中个体的更新反映了数据库碎片化匿名度的增加。此外,该文的主要贡献如下:

1.为了保证种群的多样性,该文采用包含四个亚种群的岛屿模型;

2.该文提出了两种基于集合的算子,即基于集合的变异算子和基于集合的交叉算子,将传统差分进化中的连续域转移到数据库碎片问题中的离散域;

3.在基于集合的变异算子中,每个个体的变异策略根据进化性能自适应选择;

4.实验结果表明,该文提出的S-ADDE明显优于文中比较的方法,验证了提出的算子的有效性。

实验效果

如图1所示,描述了一个样本数据库,包含九个属性和六个记录。其中数据库分为三个片段,这三个片段构成图底部所示的片段解决方案。所提出的S-ADDE算法中的每个个体代表一个数据库碎片解决方案。因此,个体中的每个位表示数据库中的一个属性,其值表示选择相应属性进行分配的片段。

图1. S-ADDE算法中的个体表示的示例

如图2所示,描述了岛屿模型的一个示例,其中每个大圆表示一个子种群。在大圆中,小三角形和圆代表最好的个体和个体其他亚群体个体。子种群中的最佳个体以预定义的迁移间隔被发送到通信拓扑上的邻域子种群。然后,随机选择每个子群体中的一个个体,并由接收到的精英个体代替。

图2. S-ADDE算法中的孤岛模型的示例

如表1所示,描述了其他方法在实验中获得的平均值和标准偏差值,最佳结果用黑体标出。可以看到,S-ADDE算法在所有测试用例上都优于其他方法,可以在探索性搜索和开发性搜索之间实现更好的平衡。但是在复杂的测试用例(如和)中,S-ADDE更容易陷入局部最优。

表1. S-ADDE算法与其他方法的比较

如图3所示,描述了四个典型测试用例的收敛曲线。其中,HA是一种针对数据库碎片问题的最先进的启发式算法,DE用作基线算法,S-DDE算法中数据库碎片问题通过基于集合的变异和交叉算子进行优化。

一开始,这三种算法都收敛得很快。HA很快陷入局部最优并停滞。由于DE和S-ADDE的探索能力,它们可以在搜索过程中不断提高匿名度。S-ADDE的绿线和DE的红线之间的差异验证了孤岛模型和所提出的基于集合的算子在S-ADDE中的有效性。

图3. 四个典型测试用例上竞争方法的收敛曲线 

如表2所示,描述了S-ADDE算法结果对原始数据集的影响。其中,AD表示每个数据集的匿名程度,min(AD)、avg(AD)和max(AD)表示由S-ADDE中的片段获得的匿名度的最小值、平均值和最大值。

表2. S-ADDE结果对原始数据集的影响

如图4所示,描述了16个测试用例的S-ADDE加速比。随着S-ADDE的并行粒度不断增加,加速比也显著增加。不同测试用例中的加速比曲线各不相同,这是因为不同的测试用例具有不同的复杂性,需要不同的评估时间。

图4. 所有测试用例的S-ADDE加速比

结语

该文定义了一个匿名驱动的数据库碎片问题。为了解决这个问题,该文提出了S-ADDE 算法。S-ADDE算法利用孤岛模型来提高种群多样性,这在复杂性高的搜索问题中至关重要。该文提出了两种基于集合的算子,即具有自适应变异策略选择的基于集合的变异算子和基于集合的交叉算子。S-ADDE的计算效率验证了所提出算子的有效性。此外,该文对数据库分片的隐私问题(即匿名度)进行了优化。在未来工作中,作者计划进一步研究和优化数据库碎片的效用问题。

作者简介

Yong-Feng Ge,分别于 2015 年和 2018 年在中国广州中山大学获得计算机科学学士、硕士学位,在华南理工大学计算机专业攻读博士学位。主要研究方向包括进化计算算法及其应用、大规模优化算法,分布式进化算法及其应用。
Jinli Cao,1997年获得澳大利亚南昆士兰大学计算机科学博士学位。目前是澳大利亚拉筹伯大学计算机科学和信息技术系的全职高级讲师。她在国际会议和期刊上发表了115多篇研究论文。主要研究方向是数据工程和信息系统,包括大数据分析、推荐系统和数据隐私保护。
王桦,2004年获得南昆士兰大学 (USQ) 计算机科学学士学位。2011年至2013年担任南昆士兰大学教授。他目前是维多利亚大学应用信息学中心的全职教授。主要研究方向包括人工智能、数据分析、数据挖掘、访问控制、隐私和 Web 服务,以及它们在电子健康和电子环境领域的应用。
陈贞翔,工学博士,济南大学教授,博士生导师,济南大学信息科学与工程学院院长,网络工程国家一流专业负责人,山东省优秀研究生导师,山东省高等学校青创科技团队带头人,济南市高校自主创新团队领军人才。主要从事计算机网络、网络安全、智能信息处理等领域研究,主持国家自然科学基金项目2项、山东省重点研发计划等省部级项目10余项。

张彦春,广州大学/鹏城实验室特聘教授,澳大利亚维多利亚大学名誉教授。多年来一直从事社会计算和电子健康,大数据与AI算法与应用研究工作,在信息技术及医学领域发表国际期刊和学术会议文400余篇。已经出版,编辑书刊和专辑20余部,完成指导相关方向40多名博士生和博士后。

 

 

期刊简介

Data Science and Engineering(DSE)是由中国计算机学会(CCF)主办、数据库专业委员会承办、施普林格自然(Springer Nature)出版的Open Access期刊。为了迎合相关领域的快速发展需求,DSE致力于出版所有和数据科学与工程领域相关的关键科学问题与前沿研究热点,以大数据作为研究重点,征稿范畴主要包括4方面:(1)数据本身,(2)数据信息提取方法,(3)数据计算理论,和(4)用来分析与管理数据的技术和系统。

目前期刊已被EI、ESCI与SCOPUS收录,CiteScore 2021为6.4,在Computer Science Applications领域排名# 157/747(位列前21%)。稿件处理费由赞助商中新赛克(Sinovatio)承担,欢迎大家免费下载阅读期刊全文,并积极投稿。

 

 

论文原文链接:https://link.springer.com/article/10.1007/s41019-021-00170-4


SCHOLAT.com 学者网
免责声明 | 关于我们 | 联系我们
联系我们: