2020年 第57卷 第2期
2020, 57(2): 241-242.
DOI: 10.7544/issn1000-1239.2020.qy0201
摘要：
近年来，随着国家和社会信息化发展的不断加速，对信息存储提出了越来越高的要求. 一方面，大数据时代，数据存储的规模和处理需求越来越高，亟需新型存储系统和技术以提供更高的性能和更好的可扩展性. 另一方面，由于各种人工智能系统及相关技术的出现，现有的存储技术和系统难以满足上层系统和技术的需求. 因此，存储系统结构技术研究面临诸多新的机遇和挑战．
基于上述背景，为促进存储领域技术交流，《计算机研究与发展》推出了本期“大数据与智能存储系统前沿技术”专题. 本期专题收录了８篇论文，分别展示了新型存储优化和大数据存储等存储领域研究热点的研究现状和最新研究成果，希望能为从事相关工作的读者提供借鉴和帮助.
近年来，随着国家和社会信息化发展的不断加速，对信息存储提出了越来越高的要求. 一方面，大数据时代，数据存储的规模和处理需求越来越高，亟需新型存储系统和技术以提供更高的性能和更好的可扩展性. 另一方面，由于各种人工智能系统及相关技术的出现，现有的存储技术和系统难以满足上层系统和技术的需求. 因此，存储系统结构技术研究面临诸多新的机遇和挑战．
基于上述背景，为促进存储领域技术交流，《计算机研究与发展》推出了本期“大数据与智能存储系统前沿技术”专题. 本期专题收录了８篇论文，分别展示了新型存储优化和大数据存储等存储领域研究热点的研究现状和最新研究成果，希望能为从事相关工作的读者提供借鉴和帮助.
2020, 57(2): 243-256.
DOI: 10.7544/issn1000-1239.2020.20190524
摘要：
非易失存储(non-volatile memory， NVM)技术的兴起给计算机存储系统带来了很多机遇与挑战.与DRAM相比，NVM作为持久性内存具有非易失、低能耗以及高存储密度等优点，但同时它也具有擦/写次数有限以及写操作延迟高等缺点，故以NVM为内存的系统需要减少对内存的写操作，以提升NVM寿命和系统性能.为了解决这个问题，提出了基于结点出度的重计算方法(re-computation scheme based on the out degree of computing nodes, ROD)，由于CPU与内存间的性能差距会导致CPU计算资源的浪费，为此ROD方法选择性地丢弃本需要存储到内存的计算结果，需要时再重新计算得到，利用计算换存储的方式减少写NVM的次数.实验采用powerstone测试集，在搭载了NVMain的Gem5模拟器中对ROD方法与贪心重计算方法和以存储为主导的无重计算方法做性能对比.结果表明ROD方法相比于存储主导的方法平均减少44.3%(最高68.5%)的写操作.ROD方法的运行耗时比存储主导的方法平均减少28.1%(最高68.6%)，比贪心重计算的方法平均减少9.3%(最高19.4%).
非易失存储(non-volatile memory， NVM)技术的兴起给计算机存储系统带来了很多机遇与挑战.与DRAM相比，NVM作为持久性内存具有非易失、低能耗以及高存储密度等优点，但同时它也具有擦/写次数有限以及写操作延迟高等缺点，故以NVM为内存的系统需要减少对内存的写操作，以提升NVM寿命和系统性能.为了解决这个问题，提出了基于结点出度的重计算方法(re-computation scheme based on the out degree of computing nodes, ROD)，由于CPU与内存间的性能差距会导致CPU计算资源的浪费，为此ROD方法选择性地丢弃本需要存储到内存的计算结果，需要时再重新计算得到，利用计算换存储的方式减少写NVM的次数.实验采用powerstone测试集，在搭载了NVMain的Gem5模拟器中对ROD方法与贪心重计算方法和以存储为主导的无重计算方法做性能对比.结果表明ROD方法相比于存储主导的方法平均减少44.3%(最高68.5%)的写操作.ROD方法的运行耗时比存储主导的方法平均减少28.1%(最高68.6%)，比贪心重计算的方法平均减少9.3%(最高19.4%).
2020, 57(2): 257-268.
DOI: 10.7544/issn1000-1239.2020.20190526
摘要：
非易失性存储器(non-volatile memory, NVM)是解决计算机系统存储墙问题的有效手段，但现有的I/O栈缺乏相应的适应和优化机制，特别是基于文件系统的锁机制是影响NVM存储系统性能的重要因素.将存储系统访问请求的管理嵌入到存储设备中，利用NVM存储设备自主管理访问请求，使用基于冲突检测的方法代替基于文件系统的现有锁机制，提高操作系统执行访问请求的并发度，缓解设备接口带来的瓶颈问题.给出了高吞吐NVM存储系统的结构，设计了一种基于二维链表的访问请求管理方法减少访问请求管理中的冲突，一种基于冲突检测的访问请求调度算法用于管理NVM存储设备中共享的访问请求，并给出了新访问请求提交和已有访问请求释放流程，并基于Intel的开源NVM存储设备模拟器PMEM实现了HTPM的原型系统，使用Filebench中的多种负载和Fio测试了HTPM的吞吐率和I/O性能，实验结果表明：HTPM相比PMEM最大能提高31.9%的IOPS值和21.4%的I/O性能.
非易失性存储器(non-volatile memory, NVM)是解决计算机系统存储墙问题的有效手段，但现有的I/O栈缺乏相应的适应和优化机制，特别是基于文件系统的锁机制是影响NVM存储系统性能的重要因素.将存储系统访问请求的管理嵌入到存储设备中，利用NVM存储设备自主管理访问请求，使用基于冲突检测的方法代替基于文件系统的现有锁机制，提高操作系统执行访问请求的并发度，缓解设备接口带来的瓶颈问题.给出了高吞吐NVM存储系统的结构，设计了一种基于二维链表的访问请求管理方法减少访问请求管理中的冲突，一种基于冲突检测的访问请求调度算法用于管理NVM存储设备中共享的访问请求，并给出了新访问请求提交和已有访问请求释放流程，并基于Intel的开源NVM存储设备模拟器PMEM实现了HTPM的原型系统，使用Filebench中的多种负载和Fio测试了HTPM的吞吐率和I/O性能，实验结果表明：HTPM相比PMEM最大能提高31.9%的IOPS值和21.4%的I/O性能.
2020, 57(2): 269-280.
DOI: 10.7544/issn1000-1239.2020.20190543
摘要：
指纹查找部分是I/O密集型工作负载，即外存存储设备的性能是指纹查找的性能瓶颈.因此关注重复数据删除系统的指纹查找部分，对比了传统的勤奋指纹查找算法和致力于减少磁盘访问次数的懒惰指纹查找算法，分析了2种方法在傲腾固态硬盘(Optane solid state drive, Optane SSD)和持久性内存(persistent memory, PM)两种新型存储设备上的性能表现，并给出了优化建议.对勤奋指纹查找算法和懒惰指纹查找算法的时间进行建模，分析得出了指纹查找算法在新型存储设备下的3点优化结论：1)应减少统一查找的指纹数;2)在较快设备上应减少懒惰指纹查找中局部性环的大小，并且局部性环大小存在一个最优值;3)在快速设备上，勤奋指纹查找的效果要优于懒惰指纹查找.最终，在实际机械硬盘(hard disk drive, HDD)、Optane SSD和PM模拟器上实验验证了模型的正确性.实验结果显示，快速设备上指纹查找的时间相较于HDD减少90%以上，并且采用勤奋算法要优于懒惰算法，局部性环最优值前移的现象，也与模型理论优化结果吻合.
指纹查找部分是I/O密集型工作负载，即外存存储设备的性能是指纹查找的性能瓶颈.因此关注重复数据删除系统的指纹查找部分，对比了传统的勤奋指纹查找算法和致力于减少磁盘访问次数的懒惰指纹查找算法，分析了2种方法在傲腾固态硬盘(Optane solid state drive, Optane SSD)和持久性内存(persistent memory, PM)两种新型存储设备上的性能表现，并给出了优化建议.对勤奋指纹查找算法和懒惰指纹查找算法的时间进行建模，分析得出了指纹查找算法在新型存储设备下的3点优化结论：1)应减少统一查找的指纹数;2)在较快设备上应减少懒惰指纹查找中局部性环的大小，并且局部性环大小存在一个最优值;3)在快速设备上，勤奋指纹查找的效果要优于懒惰指纹查找.最终，在实际机械硬盘(hard disk drive, HDD)、Optane SSD和PM模拟器上实验验证了模型的正确性.实验结果显示，快速设备上指纹查找的时间相较于HDD减少90%以上，并且采用勤奋算法要优于懒惰算法，局部性环最优值前移的现象，也与模型理论优化结果吻合.
2020, 57(2): 281-290.
DOI: 10.7544/issn1000-1239.2020.20190574
摘要：
英特尔于2019年4月正式发布基于3D-Xpoint技术的傲腾持久性内存(Optane DC persistent memory)，这为构建高效的持久性内存存储系统提供了新的机遇.然而，现有的存储系统软件并不能很好地利用其字节寻址特性，持久性内存性能很难充分发挥.提出一种文件系统数据页的混合管理机制HDPM，通过选择性使用写时复制机制和日志结构管理文件数据，充分发挥持久性内存字节可寻址特性，从而避免了传统单一模式在非对齐写或者小写造成的写放大问题.为避免影响读性能，HDPM引入逆向扫描机制，实现日志结构重构数据页时不引入额外数据拷贝.HDPM还提出一种多重垃圾回收机制进行日志清理.当单个日志结构过大时，通过读写流程主动回收日志结构；当持久性内存空间受限时，则通过后台线程使用免锁机制异步释放日志空间.实验显示，HDPM相比于NOVA文件系统，单线程写延迟降低达58%，且读延迟不受影响；Filebench多线程测试显示，HDPM相比于NOVA提升吞吐率33%.
英特尔于2019年4月正式发布基于3D-Xpoint技术的傲腾持久性内存(Optane DC persistent memory)，这为构建高效的持久性内存存储系统提供了新的机遇.然而，现有的存储系统软件并不能很好地利用其字节寻址特性，持久性内存性能很难充分发挥.提出一种文件系统数据页的混合管理机制HDPM，通过选择性使用写时复制机制和日志结构管理文件数据，充分发挥持久性内存字节可寻址特性，从而避免了传统单一模式在非对齐写或者小写造成的写放大问题.为避免影响读性能，HDPM引入逆向扫描机制，实现日志结构重构数据页时不引入额外数据拷贝.HDPM还提出一种多重垃圾回收机制进行日志清理.当单个日志结构过大时，通过读写流程主动回收日志结构；当持久性内存空间受限时，则通过后台线程使用免锁机制异步释放日志空间.实验显示，HDPM相比于NOVA文件系统，单线程写延迟降低达58%，且读延迟不受影响；Filebench多线程测试显示，HDPM相比于NOVA提升吞吐率33%.
2020, 57(2): 291-305.
DOI: 10.7544/issn1000-1239.2020.20190542
摘要：
近年来，为了避免数据因数据中心故障而永久丢失，各大机构开始尝试采用容错技术将数据存放在跨数据中心存储系统中.作为一种具有高容错性和低冗余度的容错技术，纠删码被广泛应用于单数据中心存储系统中.然而，在跨数据中心存储系统中，已有纠删码写入方法的网络资源消耗量大、编码效率低且传输效率低，这使得跨数据中心纠删码的写入速度难以适应于日益增长的数据生成速度.为提高跨数据中心纠删码的写入速度，提出了一种基于生成矩阵变换的跨数据中心纠删码写入方法(cross-datacenter erasure code writing method based on generator matrix transformation, CREW).通过对传输拓扑和生成矩阵进行优化，CREW可使写入过程中需要长距离传输的数据块尽可能地少，从而达到降低网络资源消耗量的目的.通过在数据中心间采用分布式的数据传输和数据编码、在各数据中心内部采用集中式的数据传输和数据编码，CREW可在编码效率和传输效率间取得较好权衡.在跨数据中心环境下的实验表明：与2种广泛使用的传统纠删码写入方法相比，CREW的写入速度提高了36.3%~57.9%；与现有的跨数据中心纠删码写入方法IncEncoding相比，CREW的写入速度提高了32.4%.
近年来，为了避免数据因数据中心故障而永久丢失，各大机构开始尝试采用容错技术将数据存放在跨数据中心存储系统中.作为一种具有高容错性和低冗余度的容错技术，纠删码被广泛应用于单数据中心存储系统中.然而，在跨数据中心存储系统中，已有纠删码写入方法的网络资源消耗量大、编码效率低且传输效率低，这使得跨数据中心纠删码的写入速度难以适应于日益增长的数据生成速度.为提高跨数据中心纠删码的写入速度，提出了一种基于生成矩阵变换的跨数据中心纠删码写入方法(cross-datacenter erasure code writing method based on generator matrix transformation, CREW).通过对传输拓扑和生成矩阵进行优化，CREW可使写入过程中需要长距离传输的数据块尽可能地少，从而达到降低网络资源消耗量的目的.通过在数据中心间采用分布式的数据传输和数据编码、在各数据中心内部采用集中式的数据传输和数据编码，CREW可在编码效率和传输效率间取得较好权衡.在跨数据中心环境下的实验表明：与2种广泛使用的传统纠删码写入方法相比，CREW的写入速度提高了36.3%~57.9%；与现有的跨数据中心纠删码写入方法IncEncoding相比，CREW的写入速度提高了32.4%.
2020, 57(2): 306-317.
DOI: 10.7544/issn1000-1239.2020.20190549
摘要：
硬盘故障是数据中心最主要的故障，严重影响了可靠性.传统的数据容错技术一般都是通过增加数据冗余来实现的，存在缺陷.主动容错技术通过预测硬盘故障提前将数据迁移，成为研究热点.现有技术大多研究硬盘故障预测，缺乏采集、迁移、反馈的研究，难以商用.提出“采集—预测—迁移—反馈”全流程主动容错机制，包括：分时硬盘信息采集方法、滑动窗口记录合并及样本构建方法、多类型硬盘故障预测方法、多盘联合数据迁移方法、预测结果二级验证及快速反馈方法.测试表明：采集硬盘信息对业务影响仅0.96%，硬盘故障预测召回率达94.66%，数据修复时间较传统方法减少55.10%.该工作已在中兴通讯的数据中心稳定商用，满足了主动容错技术在高可靠、高智能、低干扰、低成本、广适用等核心目标.
硬盘故障是数据中心最主要的故障，严重影响了可靠性.传统的数据容错技术一般都是通过增加数据冗余来实现的，存在缺陷.主动容错技术通过预测硬盘故障提前将数据迁移，成为研究热点.现有技术大多研究硬盘故障预测，缺乏采集、迁移、反馈的研究，难以商用.提出“采集—预测—迁移—反馈”全流程主动容错机制，包括：分时硬盘信息采集方法、滑动窗口记录合并及样本构建方法、多类型硬盘故障预测方法、多盘联合数据迁移方法、预测结果二级验证及快速反馈方法.测试表明：采集硬盘信息对业务影响仅0.96%，硬盘故障预测召回率达94.66%，数据修复时间较传统方法减少55.10%.该工作已在中兴通讯的数据中心稳定商用，满足了主动容错技术在高可靠、高智能、低干扰、低成本、广适用等核心目标.
2020, 57(2): 318-332.
DOI: 10.7544/issn1000-1239.2020.20190563
摘要：
通过数据分析发现海量数据中的潜在价值，能够带来巨大的收益.Spark具有良好的系统扩展性与处理性能，因而被广泛运用于大数据分析.Spark SQL是Spark最常用的编程接口.在数据分析应用中存在着大量的重复计算，这些重复计算不仅浪费系统资源，而且导致查询运行效率低.但是Spark SQL无法感知查询语句之间的重复计算.为此，提出了基于收益模型的、细粒度的自动数据重用机制Criss以减少重复计算.针对混合介质，提出了感知异构I/O性能的收益模型用于自动识别重用收益最大的算子计算结果，并采用Partition粒度的数据重用和缓存管理，以提高查询效率和缓存空间的利用率，充分发挥数据重用的优势.基于Spark SQL和TachyonFS，实现了Criss系统.实验结果表明：Criss的查询性能比原始Spark SQL提升了46%~68%.
通过数据分析发现海量数据中的潜在价值，能够带来巨大的收益.Spark具有良好的系统扩展性与处理性能，因而被广泛运用于大数据分析.Spark SQL是Spark最常用的编程接口.在数据分析应用中存在着大量的重复计算，这些重复计算不仅浪费系统资源，而且导致查询运行效率低.但是Spark SQL无法感知查询语句之间的重复计算.为此，提出了基于收益模型的、细粒度的自动数据重用机制Criss以减少重复计算.针对混合介质，提出了感知异构I/O性能的收益模型用于自动识别重用收益最大的算子计算结果，并采用Partition粒度的数据重用和缓存管理，以提高查询效率和缓存空间的利用率，充分发挥数据重用的优势.基于Spark SQL和TachyonFS，实现了Criss系统.实验结果表明：Criss的查询性能比原始Spark SQL提升了46%~68%.
2020, 57(2): 333-345.
DOI: 10.7544/issn1000-1239.2020.20190565
摘要：
近年来，随着智能目标识别、电子传感器、协同控制以及计算机网络等先进技术的快速发展，智能交通系统实现了质的飞越，现代智能交通系统可以实现车、路、云端于一体的智能交通运输管理平台.但智能交通系统依赖于每天产生的大量的2维地理空间信息数据，因此，如何对大规模的地理空间数据进行高效的存储和查询对智能交通系统未来的普及和发展具有重要意义.然而，由于城市交通信息的复杂性、数据量大、更新速度快等特征，当前的空间索引技术很难针对2维地理空间信息数据进行高效的检索.为了优化空间大数据下2维地理空间信息数据的存储组织结构、提高检索效率，提出了一种对2维地理空间信息数据进行多层切片递归的空间索引树构造算法(multi-layer slice recursive, MSR).提出的算法首先对地图数据第1维度进行排序划分切片，生成FD(first division)切片；然后对FD切片中的地图数据进行第2维度排序，生成SD(second division)切片，在SD切片中对当前切片和相邻切片划分空间对象；最后对空间对象长度与节点容量比较进行数据聚类操作，通过判断所有切片是否完成聚类操作，自下而上递归生成MSR 树.实验表明，MSR算法构建的2维空间存储结构的查询性能优于现在最具代表性的空间索引技术基于R树的批量加载算法(sort tile recursive， STR)、STR-网格混合算法(str-grid)及高效几何范围查询算法(efficient geometric range query, EGRQ).
近年来，随着智能目标识别、电子传感器、协同控制以及计算机网络等先进技术的快速发展，智能交通系统实现了质的飞越，现代智能交通系统可以实现车、路、云端于一体的智能交通运输管理平台.但智能交通系统依赖于每天产生的大量的2维地理空间信息数据，因此，如何对大规模的地理空间数据进行高效的存储和查询对智能交通系统未来的普及和发展具有重要意义.然而，由于城市交通信息的复杂性、数据量大、更新速度快等特征，当前的空间索引技术很难针对2维地理空间信息数据进行高效的检索.为了优化空间大数据下2维地理空间信息数据的存储组织结构、提高检索效率，提出了一种对2维地理空间信息数据进行多层切片递归的空间索引树构造算法(multi-layer slice recursive, MSR).提出的算法首先对地图数据第1维度进行排序划分切片，生成FD(first division)切片；然后对FD切片中的地图数据进行第2维度排序，生成SD(second division)切片，在SD切片中对当前切片和相邻切片划分空间对象；最后对空间对象长度与节点容量比较进行数据聚类操作，通过判断所有切片是否完成聚类操作，自下而上递归生成MSR 树.实验表明，MSR算法构建的2维空间存储结构的查询性能优于现在最具代表性的空间索引技术基于R树的批量加载算法(sort tile recursive， STR)、STR-网格混合算法(str-grid)及高效几何范围查询算法(efficient geometric range query, EGRQ).
2020, 57(2): 346-362.
DOI: 10.7544/issn1000-1239.2020.20190455
摘要：
大规模数据收集大幅提升了机器学习算法的性能，实现了经济效益和社会效益的共赢，但也令个人隐私保护面临更大的风险与挑战.机器学习的训练模式主要分为集中学习和联邦学习2类，前者在模型训练前需统一收集各方数据，尽管易于部署，却存在极大数据隐私与安全隐患；后者实现了将各方数据保留在本地的同时进行模型训练，但该方式目前正处于研究的起步阶段，无论在技术还是部署中仍面临诸多问题与挑战.现有的隐私保护技术研究大致分为2条主线，即以同态加密和安全多方计算为代表的加密方法和以差分隐私为代表的扰动方法，二者各有利弊.为综述当前机器学习的隐私问题，并对现有隐私保护研究工作进行梳理和总结，首先分别针对传统机器学习和深度学习2类情况，探讨集中学习下差分隐私保护的算法设计；之后概述联邦学习中存在的隐私问题及保护方法；最后总结目前隐私保护中面临的主要挑战，并着重指出隐私保护与模型可解释性研究、数据透明之间的问题与联系.
大规模数据收集大幅提升了机器学习算法的性能，实现了经济效益和社会效益的共赢，但也令个人隐私保护面临更大的风险与挑战.机器学习的训练模式主要分为集中学习和联邦学习2类，前者在模型训练前需统一收集各方数据，尽管易于部署，却存在极大数据隐私与安全隐患；后者实现了将各方数据保留在本地的同时进行模型训练，但该方式目前正处于研究的起步阶段，无论在技术还是部署中仍面临诸多问题与挑战.现有的隐私保护技术研究大致分为2条主线，即以同态加密和安全多方计算为代表的加密方法和以差分隐私为代表的扰动方法，二者各有利弊.为综述当前机器学习的隐私问题，并对现有隐私保护研究工作进行梳理和总结，首先分别针对传统机器学习和深度学习2类情况，探讨集中学习下差分隐私保护的算法设计；之后概述联邦学习中存在的隐私问题及保护方法；最后总结目前隐私保护中面临的主要挑战，并着重指出隐私保护与模型可解释性研究、数据透明之间的问题与联系.
2020, 57(2): 363-377.
DOI: 10.7544/issn1000-1239.2020.20190018
摘要：
各类移动社交网络应用的发展促使了海量网络用户的出现,从而形成了大规模的社交图结构数据.这些图结构数据中包含着大量的用户隐私信息,因此发布之前需要进行隐私保护处理以防数据遭到泄露.同时,用户间错综复杂的社交关系并非均等,个体间关系的强弱可能直接影响到隐私的分布和保护的效率.目前存在相当多的针对无权值的社交网络图数据的隐私保护方法,但这些方法不能直接应用于带权值(社交关系敏感程度不均等)的社交网络图数据中.为解决这一问题,提出一种基于非交互的差分隐私保护模型的带权值的社交网络图扰动方法dp-noisy,可实现对边权值以及图结构的强保护.该方法基于单源最短路径约束模型来添加扰动噪音,根据不同的权值划分出关键边和非关键边,有效减少了需要扰动的边关系.实验结果表明:在大规模数据集中(节点数为30 000),dp-noisy在运行效率上比K-MPNP(K-shortest path privacy)提高了47.3%,比LWSPA(protection algorithm based on Laplace noise for weighted social networks)提高了41.8%,比DER(density-based exploration and reconstruc-tion)提高了52.6%.在相似的数据隐私保护程度下,dp-noisy的数据可用性比lp-noisy提高了10%,显著优于DER的数据可用性,略好于LWSPA.此外,dp-noisy的平均扰动质量比lp-noisy提高了14%,比DER提高了11.3%,比K-MPNP提高了27%; 在达到最优数据效用时(ε=10),dp-noisy的平均扰动质量比LWSPA提高了6%.综上,dp-noisy具有较高的运行效率和数据效用,同时满足抵御图结构攻击的特性,可适用于大规模的社交网络数据分析.
各类移动社交网络应用的发展促使了海量网络用户的出现,从而形成了大规模的社交图结构数据.这些图结构数据中包含着大量的用户隐私信息,因此发布之前需要进行隐私保护处理以防数据遭到泄露.同时,用户间错综复杂的社交关系并非均等,个体间关系的强弱可能直接影响到隐私的分布和保护的效率.目前存在相当多的针对无权值的社交网络图数据的隐私保护方法,但这些方法不能直接应用于带权值(社交关系敏感程度不均等)的社交网络图数据中.为解决这一问题,提出一种基于非交互的差分隐私保护模型的带权值的社交网络图扰动方法dp-noisy,可实现对边权值以及图结构的强保护.该方法基于单源最短路径约束模型来添加扰动噪音,根据不同的权值划分出关键边和非关键边,有效减少了需要扰动的边关系.实验结果表明:在大规模数据集中(节点数为30 000),dp-noisy在运行效率上比K-MPNP(K-shortest path privacy)提高了47.3%,比LWSPA(protection algorithm based on Laplace noise for weighted social networks)提高了41.8%,比DER(density-based exploration and reconstruc-tion)提高了52.6%.在相似的数据隐私保护程度下,dp-noisy的数据可用性比lp-noisy提高了10%,显著优于DER的数据可用性,略好于LWSPA.此外,dp-noisy的平均扰动质量比lp-noisy提高了14%,比DER提高了11.3%,比K-MPNP提高了27%; 在达到最优数据效用时(ε=10),dp-noisy的平均扰动质量比LWSPA提高了6%.综上,dp-noisy具有较高的运行效率和数据效用,同时满足抵御图结构攻击的特性,可适用于大规模的社交网络数据分析.
2020, 57(2): 378-394.
DOI: 10.7544/issn1000-1239.2020.20190104
摘要：
密度峰值聚类(density peak, DPeak)算法是一种简单有效的聚类算法，它可将任意维度数据映射成2维，在降维后的空间中建构出数据之间的层次关系，可以非常容易地从中挑选出密度高、且与其他密度更高区域相隔较远的数据点.这些点被称为密度峰值点，可以用来作为聚类中心.根据建构好的层次关系,该算法提供了2种不同的方式完成最后聚类:一种是与用户交互的决策图，另一种是自动化方式.跟踪了DPeak近年来的发展与应用动态，对该算法的各种改进或变种从以下3方面进行了总结和梳理：首先，介绍了DPeak算法原理，对其在聚类算法分类体系中的位置进行了讨论.将其与5个主要的聚类算法做了比较之后，发现DPeak与均值漂移聚类算法(mean shift)有诸多相似之处，因而认为其可能为mean shift的一个特殊变种.其次，讨论了DPeak的几个不足之处，如复杂度较高、自适应性不足、精度低和高维数据适用性差等，将针对这些缺点进行改进的相关算法做了分类讨论.此外，梳理了DPeak算法在不同领域中的应用,如自然语言处理、生物医学应用、光学应用等.最后，探讨了密度峰值聚类算法所存在的问题及挑战，同时对进一步的工作进行展望.
密度峰值聚类(density peak, DPeak)算法是一种简单有效的聚类算法，它可将任意维度数据映射成2维，在降维后的空间中建构出数据之间的层次关系，可以非常容易地从中挑选出密度高、且与其他密度更高区域相隔较远的数据点.这些点被称为密度峰值点，可以用来作为聚类中心.根据建构好的层次关系,该算法提供了2种不同的方式完成最后聚类:一种是与用户交互的决策图，另一种是自动化方式.跟踪了DPeak近年来的发展与应用动态，对该算法的各种改进或变种从以下3方面进行了总结和梳理：首先，介绍了DPeak算法原理，对其在聚类算法分类体系中的位置进行了讨论.将其与5个主要的聚类算法做了比较之后，发现DPeak与均值漂移聚类算法(mean shift)有诸多相似之处，因而认为其可能为mean shift的一个特殊变种.其次，讨论了DPeak的几个不足之处，如复杂度较高、自适应性不足、精度低和高维数据适用性差等，将针对这些缺点进行改进的相关算法做了分类讨论.此外，梳理了DPeak算法在不同领域中的应用,如自然语言处理、生物医学应用、光学应用等.最后，探讨了密度峰值聚类算法所存在的问题及挑战，同时对进一步的工作进行展望.
2020, 57(2): 395-412.
DOI: 10.7544/issn1000-1239.2020.20190092
摘要：
虹膜识别是生物特征识别中最稳定和最可靠的身份识别方法之一.在虹膜识别的整个流程中，虹膜分割处于预处理阶段，因此虹膜分割结果的好坏将直接影响虹膜识别的精度.自从1993年Daugman第1次提出高性能的虹膜识别系统以来，各种各样的虹膜分割算法陆续提出，尤其是近年来基于深度学习的虹膜分割算法极大地提升了虹膜分割的精度.然而，由于缺乏统一的数据库和评价指标，各种算法的性能比较杂乱而不公平，因此提出了一个公开的虹膜分割评价基准.首先，介绍了虹膜分割的定义和面临的挑战；其次全面梳理了3个有代表性的公开虹膜分割数据库，总结了其特点和挑战性；紧接着定义了虹膜分割的评价指标；然后对传统的和基于深度学习的虹膜分割算法进行了总结，并通过详细的实验对各类算法进行了比较和分析.实验结果表明：当前基于深度学习的虹膜分割算法在准确性上超越了传统的方法.最后，对基于深度学习的虹膜分割算法存在的问题进行了思考和讨论.
虹膜识别是生物特征识别中最稳定和最可靠的身份识别方法之一.在虹膜识别的整个流程中，虹膜分割处于预处理阶段，因此虹膜分割结果的好坏将直接影响虹膜识别的精度.自从1993年Daugman第1次提出高性能的虹膜识别系统以来，各种各样的虹膜分割算法陆续提出，尤其是近年来基于深度学习的虹膜分割算法极大地提升了虹膜分割的精度.然而，由于缺乏统一的数据库和评价指标，各种算法的性能比较杂乱而不公平，因此提出了一个公开的虹膜分割评价基准.首先，介绍了虹膜分割的定义和面临的挑战；其次全面梳理了3个有代表性的公开虹膜分割数据库，总结了其特点和挑战性；紧接着定义了虹膜分割的评价指标；然后对传统的和基于深度学习的虹膜分割算法进行了总结，并通过详细的实验对各类算法进行了比较和分析.实验结果表明：当前基于深度学习的虹膜分割算法在准确性上超越了传统的方法.最后，对基于深度学习的虹膜分割算法存在的问题进行了思考和讨论.
2020, 57(2): 413-423.
DOI: 10.7544/issn1000-1239.2020.20190333
摘要：
在衍射成像光谱仪成像过程中，准焦谱段成像会受到其他离焦谱段的干扰而产生模糊.现有的重构算法只利用了图像空间信息，并且对于此类不适定反问题的复原效果不佳.因此，提出了一种基于多通道空间光谱全变差的正则化方法来重构衍射光谱图像.首先根据衍射光谱成像原理构建退化光谱图像的观测模型，然后在最大后验概率框架下结合空间和光谱先验信息建立复原模型.该方法充分利用衍射光谱图像的局部空间平滑性和局部光谱平滑性，并使用交替方向乘子法对模型进行有效的优化.大量实验表明，与其他的衍射光谱图像重构方法相比，此复原模型在平均峰值信噪比、平均结构相似度、平均光谱角距离和视觉质量方面都具有一定的优越性.此外，对于多通道模糊重叠且受噪声干扰的病态问题，该模型能够在保证求解速度的情况下抑制噪声，保留边缘信息，减缓锯齿状光谱失真的情况.
在衍射成像光谱仪成像过程中，准焦谱段成像会受到其他离焦谱段的干扰而产生模糊.现有的重构算法只利用了图像空间信息，并且对于此类不适定反问题的复原效果不佳.因此，提出了一种基于多通道空间光谱全变差的正则化方法来重构衍射光谱图像.首先根据衍射光谱成像原理构建退化光谱图像的观测模型，然后在最大后验概率框架下结合空间和光谱先验信息建立复原模型.该方法充分利用衍射光谱图像的局部空间平滑性和局部光谱平滑性，并使用交替方向乘子法对模型进行有效的优化.大量实验表明，与其他的衍射光谱图像重构方法相比，此复原模型在平均峰值信噪比、平均结构相似度、平均光谱角距离和视觉质量方面都具有一定的优越性.此外，对于多通道模糊重叠且受噪声干扰的病态问题，该模型能够在保证求解速度的情况下抑制噪声，保留边缘信息，减缓锯齿状光谱失真的情况.
2020, 57(2): 424-432.
DOI: 10.7544/issn1000-1239.2020.20190281
摘要：
关联关系挖掘与发现是大数据挖掘与分析的重要基础，现有的关联关系挖掘方法多是对数据进行统计分析，对未知数据缺少关联判别作用.尝试从学习的角度进行关联关系挖掘，给出了关联学习的形式化定义和相关概念，并根据关联学习定义构建学习数据集.具体地构建了2类关联图像数据集(two class associated image data sets, TAID)，利用卷积神经网络提取关联特征，然后分别用softmax函数和K近邻算法判别关联关系，基于此提出3种关联关系判别器:关联图像卷积神经网络判别器(associated image convolutional neural network discriminator, AICNN)、关联图像LeNet判别器(associated image LeNet discriminator, AILeNet)和关联图像K近邻判别器(associated image K-nearest neighbor discriminator, AIKNN).3种关联判别器在TAID数据集上进行测试，AICNN在64×64像素90 000个训练样本上的判别精度达0.821 7,AILeNet在256×256像素22 500个训练样本上的判别精度达0.845 6，AIKNN在256×256像素22 500个训练样本上的判别精度达到0.866 4.这3种关联判别器有效地证明了学习角度挖掘关联关系的可行性.
关联关系挖掘与发现是大数据挖掘与分析的重要基础，现有的关联关系挖掘方法多是对数据进行统计分析，对未知数据缺少关联判别作用.尝试从学习的角度进行关联关系挖掘，给出了关联学习的形式化定义和相关概念，并根据关联学习定义构建学习数据集.具体地构建了2类关联图像数据集(two class associated image data sets, TAID)，利用卷积神经网络提取关联特征，然后分别用softmax函数和K近邻算法判别关联关系，基于此提出3种关联关系判别器:关联图像卷积神经网络判别器(associated image convolutional neural network discriminator, AICNN)、关联图像LeNet判别器(associated image LeNet discriminator, AILeNet)和关联图像K近邻判别器(associated image K-nearest neighbor discriminator, AIKNN).3种关联判别器在TAID数据集上进行测试，AICNN在64×64像素90 000个训练样本上的判别精度达0.821 7,AILeNet在256×256像素22 500个训练样本上的判别精度达0.845 6，AIKNN在256×256像素22 500个训练样本上的判别精度达到0.866 4.这3种关联判别器有效地证明了学习角度挖掘关联关系的可行性.
2020, 57(2): 433-446.
DOI: 10.7544/issn1000-1239.2020.20190160
摘要：
域名生成算法(domain generation algorithm, DGA)是域名检测中防范僵尸网络攻击的重要手段之一，对于生成威胁情报、阻断僵尸网络命令与控制流量、保障网络安全有重要的实际意义.近年来，DGA域名检测技术从依靠手工提取特征发展到自动提取特征的基于深度学习模型的方法，在DGA域名检测任务中取得了较大的进展.但对于不同僵尸网络家族的DGA域名的多分类任务，由于家族种类多，且各家族域名数据存在不平衡性，因此许多已有的深度学习模型在DGA域名的多分类任务上仍有提高空间.针对以上挑战，设计了基于字符和双字母组级别的混合词向量，以提高域名字符串的信息利用度，并设计了基于混合词向量方法的深度学习模型.最后设计了包含多种对比模型的实验，对混合词向量的有效性进行验证.实验结果表明基于混合词向量的深度学习模型在DGA域名检测与分类任务中相比只基于字符级词向量的模型有更好的分类性能，特别是在小样本的DGA域名类别上的分类性能更优，证明了该模型的有效性.
域名生成算法(domain generation algorithm, DGA)是域名检测中防范僵尸网络攻击的重要手段之一，对于生成威胁情报、阻断僵尸网络命令与控制流量、保障网络安全有重要的实际意义.近年来，DGA域名检测技术从依靠手工提取特征发展到自动提取特征的基于深度学习模型的方法，在DGA域名检测任务中取得了较大的进展.但对于不同僵尸网络家族的DGA域名的多分类任务，由于家族种类多，且各家族域名数据存在不平衡性，因此许多已有的深度学习模型在DGA域名的多分类任务上仍有提高空间.针对以上挑战，设计了基于字符和双字母组级别的混合词向量，以提高域名字符串的信息利用度，并设计了基于混合词向量方法的深度学习模型.最后设计了包含多种对比模型的实验，对混合词向量的有效性进行验证.实验结果表明基于混合词向量的深度学习模型在DGA域名检测与分类任务中相比只基于字符级词向量的模型有更好的分类性能，特别是在小样本的DGA域名类别上的分类性能更优，证明了该模型的有效性.
2020, 57(2): 447-458.
DOI: 10.7544/issn1000-1239.2020.20190279
摘要：
现有的多粒度标记形式背景将所有属性的粒度标记值通过多个单粒度标记形式背景的并置予以表示，这可能导致后续相关问题的研究主要集中于多个单粒度标记形式背景的知识发现及其相互关系，不利于挖掘多粒度标记形式背景的多层次知识.通过重构单粒度标记形式背景的属性粒度标记值，在多粒度标记形式背景中研究介粒度标记形式背景，使得知识发现不仅仅局限于数据采集或表示所形成的粗细粒度标记数据，还包括跨粒度重组数据的知识发现.首先，提出介粒度标记形式背景的概念，给出相应的语义解释；其次，讨论介粒度标记形式背景的泛化与特化，在此基础上证明所有介粒度标记形式背景在泛化-特化关系下构成一个完备格；然后，给出多粒度标记决策形式背景的介粒度知识发现方法，得到粗细介粒度标记形式背景之间的决策蕴涵诱导关系；最后，实验分析表明介粒度标记方法的有效性和优势所在.
现有的多粒度标记形式背景将所有属性的粒度标记值通过多个单粒度标记形式背景的并置予以表示，这可能导致后续相关问题的研究主要集中于多个单粒度标记形式背景的知识发现及其相互关系，不利于挖掘多粒度标记形式背景的多层次知识.通过重构单粒度标记形式背景的属性粒度标记值，在多粒度标记形式背景中研究介粒度标记形式背景，使得知识发现不仅仅局限于数据采集或表示所形成的粗细粒度标记数据，还包括跨粒度重组数据的知识发现.首先，提出介粒度标记形式背景的概念，给出相应的语义解释；其次，讨论介粒度标记形式背景的泛化与特化，在此基础上证明所有介粒度标记形式背景在泛化-特化关系下构成一个完备格；然后，给出多粒度标记决策形式背景的介粒度知识发现方法，得到粗细介粒度标记形式背景之间的决策蕴涵诱导关系；最后，实验分析表明介粒度标记方法的有效性和优势所在.
本刊虚拟专辑J-CRAD Transactions on系列更新，欢迎阅读！
