软件学报杂志

软件学报杂志2025年第2期

• 状态转换图制导的ARP错误检测方法

  林高毅，崔展齐，陈翔，郑丽伟

  Android应用开发人员需要在保持应用频繁更新的同时快速检测出应用中Android运行时权限(Android runtime permission, ARP)错误. 现有的Android应用自动化测试工具通常未考虑ARP机制, 无法有效测试Android应用内的权限相关行为. 为帮助开发人员快速检测出应用中ARP错误, 提出状态转换图制导的Android应用运行时权限错误检测方法. 首先, 对被测应用APK文件进行权限误用分析, 插桩APK文件中可能导致ARP错误的API, 并对APK文件重新签名; 然后, 安装插桩后的APK文件, 动态探索应用以生成其状态转换图(state transition graph, STG); 最后, 使用STG制导自动化测试, 快速检测出应用中ARP错误. 基于所提出方法实现原型工具RPBDroid, 并与ARP错误动态检测工具SetDroid、PermDroid和传统自动化测试工具APE进行对比实验. 实验结果表明, RPBDroid成功检测出17个应用中的15个ARP错误, 比APE、SetDroid、PermDroid分别多14、12和14个. 此外, 相比于测试工具SetDroid、PermDroid和APE, RPBDroid检测ARP错误的平均用时分别减少86.42%、86.72%和86.70%.

• FineFlow: FaaS工作流部署优化与执行系统

  刘璐，高浩城，陈伟，吴国全，魏峻

  FaaS (function-as-a-service, 函数即服务)工作流由多个函数服务编排而成, 通过对多个函数的协调控制来实现复杂的业务应用. 当前FaaS工作流系统主要基于集中式的数据存储实现函数间的数据传递, 导致FaaS函数间的数据传输开销大, 显著影响应用性能. 在高并发情况下, 频繁的数据传输还会产生严重的网络带宽资源争用, 导致应用性能下降. 针对上述问题, 基于函数服务间的细粒度数据依赖分析, 提出一种基于关键路径的函数部署优化方法, 设计了依赖敏感的数据存取与管理机制, 有效减少函数间数据传输, 从而降低FaaS工作流应用执行的数据传输时延和端到端时延. 设计实现了FaaS工作流系统FineFlow, 并基于5个真实FaaS工作流应用开展实验评估. 实验结果表明, 相比于基于集中式数据存储函数交互机制的FaaS工作流平台, FineFlow能够有效降低FaaS工作流应用的数据传输时延: 最高降低74.6%, 平均降低63.8%; 平均降低应用端到端执行时延19.6%. 特别地, 对于具有明显细粒度数据依赖的FaaS工作流应用, 相比于现有的基于数据本地性的优化方法, FineFlow能够使数据传输时延和端到端时延进一步分别降低28.4%和13.8%. 此外, FineFlow通过减少跨节点的数据传输, 能够有效缓解网络带宽波动对FaaS工作流执行性能的影响, 提升应用性能受网络带宽影响的鲁棒性.

• 开源软件供应链漏洞威胁智能感知

  王丽敏，吴敬征，武延军，芮志清，罗天悦，屈晟，杨牧天

  开源软件的繁荣推动了软件领域的蓬勃发展, 也促使以开源软件为基础的供应链开发模式的形成. 开源软件供应链本质上是个复杂的供应链拓扑网络, 由开源生态的关键元素及其关联关系构成, 其产品全球化等优势有助于提高软件行业的开发效率. 然而, 开源软件供应链也存在依赖关系复杂、传播范围广泛、攻击面暴露扩大等特点, 带来了新的安全风险. 现有的以安全漏洞、威胁情报为基础的安全管理虽然可以实现安全预警、预先防御, 但是由于漏洞威胁信息获取不及时、缺少攻击技术和缓解措施等信息, 严重影响了漏洞处理效率. 针对上述问题, 设计并实现一种针对开源软件供应链的漏洞威胁智能感知方法, 包括两部分: 1)构建CTI (网络威胁情报)知识图谱, 在其构建的过程中使用到相关技术, 可以实现安全情报的实时分析与处理, 尤其提出SecERNIE模型以及软件包命名矩阵, 分别缓解漏洞威胁关联挖掘的问题和开源软件别名的问题. 2)漏洞风险信息推送, 以软件包命名矩阵为基础, 构建软件包过滤规则, 实现开源系统漏洞实时过滤与推送. 通过实验验证所提方法的有效性和可用性. 实验结果显示, 相较于NVD等传统漏洞平台, 本方法平均感知时间最高提前90.03天; 在操作系统软件覆盖率上提升74.37%, 并利用SecERNIE模型实现63492个CVE漏洞与攻击技术实体之间的关联关系映射. 特别地, 针对openEuler操作系统, 可追踪的系统软件覆盖率达到92.76%, 并累计感知6239个安全漏洞; 同时, 还发现openEuler中891条漏洞与攻击的关联关系, 进而获取到相应的解决方案, 为漏洞处理提供了参考依据. 在真实攻击环境验证2种典型的攻击场景, 证明所提方法在漏洞威胁感知方面的良好的效果.

• 多模态可信度感知的情感计算

  罗佳敏，王晶晶，周国栋

  多模态情感计算是情感计算领域一个基础且重要的研究任务, 旨在利用多模态信号对用户生成的视频进行情感理解. 尽管已有的多模态情感计算方法在基准数据集上取得了不错的性能, 但这些方法无论是设计复杂的融合策略还是学习模态表示, 普遍忽视了多模态情感计算任务中存在的模态可信度偏差问题. 认为相较于文本, 语音和视觉模态往往能更真实的表达情感, 因而在情感计算任务中, 语音和视觉是高可信度的, 文本是低可信度的. 然而, 已有的针对不同模态特征抽取工具的学习能力不同, 导致文本模态表示能力往往强于语音和视觉模态(例如: GPT3与ResNet), 这进一步加重了模态可信度偏差问题, 不利于高精度的情感判断. 为缓解模态可信度偏差, 提出一种模型无关的基于累积学习的多模态可信度感知的情感计算方法, 通过为低可信度的文本模态设计单独的文本模态分支捕捉偏差, 让模型在学习过程中从关注于低可信度文本模态的情感逐步关注到高可信度语音和视觉模态的情感, 从而有效缓解低可信度文本模态导致的情感预测不准确. 在多个基准数据集上进行实验, 多组对比实验的结果表明, 所提出的方法能够有效地突出高可信度语音和视觉模态的重要性, 缓解低可信度文本模态的偏差; 并且, 该模型无关的方法显著提升了多模态情感计算方法的性能, 这表明所提方法在多模态情感计算任务中的有效性和通用性.

• 基于元属性学习的事件检测

  贺瑞芳，马劲松，黄孝家，张仕奇，白洁

  事件检测旨在识别非结构化文本中的事件触发词, 并将其分类为预定义的事件类别, 可用于知识图谱构建及舆情监控等. 然而, 其中的数据稀疏和不平衡问题严重影响了事件检测系统的性能和可用性. 现有大多数方法没有很好地解决这一问题, 这源于其将不同类别的事件独立看待, 并通过分类器或空间距离对触发词进行识别和分类. 尽管有研究考虑事件大类下子类的事件元素存在关联性, 采用多任务学习进行互增强, 但忽略了不同类别事件触发词之间的共享属性. 已有相关建模事件类别关系的工作需要大量的规则设计和数据标注, 导致作用域局限, 泛化性不强. 因此, 提出一种基于元属性的事件检测方法. 其旨在学习不同类别样本中包含的共享内在信息, 包括: (1) 构造触发词的特殊符号表示并通过表示向量的映射来提取触发词的类别无关语义; (2) 拼接触发词表示, 类别的样本语义表示和类别的标签语义表示, 输入一个可训练的相似度度量层, 从而建模关于触发词和事件类别的公用相似度度量. 通过学习以上两种信息以缓解数据稀疏和不平衡的影响. 此外, 将样本的类别无关语义集成到分类方法中, 并构建完整的融合模型. 在ACE2005和MAVEN数据集上通过不同程度稀疏和不平衡情景下的实验证明所提出方法的有效性, 并建立传统和少样本设置之间的联系.

• 基于路径签名的时间序列领域自适应方法

  蔡瑞初，颜嘉文，陈道鑫，李梓健，郝志峰

  近年来深度学习因其在各个场景下的优异性能而受到越来越多研究者的重视, 但是这些方法通常依赖独立同分布假设. 领域自适应则是为了缓解分布偏移带来的影响而提出的问题, 它利用带标签的源域数据和不带标签的目标域数据能够训练得到在目标域数据上性能较好的模型. 现有的领域自适应方法大多针对静态数据, 而时间序列数据的方法需要捕捉变量之间的依赖关系. 现有的方法虽然采用针对时间序列数据的特征提取器, 例如递归神经网络, 以学习变量间的依赖关系, 但是往往将冗余的信息也一同提取. 这些冗余信息容易和语义信息耦合, 进而影响模型的预测性能. 基于上述问题, 提出一种基于路径签名的时间序列领域自适应方法(path-signature-based time-series domain adaptation, PSDA). 该方法一方面利用路径签名变换来捕捉变量间的稀疏依赖关系, 排除冗余相关关系的同时保留语义相关关系, 从而有利于提取时序数据中具有判别力的特征; 另一方面通过约束源域和目标域之间的依赖关系一致性来保留领域之间不变的依赖关系, 排除领域变化的依赖关系, 从而有利于提取时序数据中具有泛化性的特征. 基于以上方法, 进一步提出一个距离度量标准和泛化性边界理论, 并且在多个时间序列领域自适应标准数据集上获得了最好的实验效果.

• 面向参数化动作空间的多智能体中心化策略梯度分解及其应用

  田树聪，谢愈，张远龙，周正春，高阳

  近年来, 多智能体强化学习方法凭借AlphaStar、AlphaDogFight、AlphaMosaic等成功案例展示出卓越的决策能力以及广泛的应用前景. 在真实环境的多智能体决策系统中, 其任务的决策空间往往是同时具有离散型动作变量和连续型动作变量的参数化动作空间. 这类动作空间的复杂性结构使得传统单一针对离散型或连续型的多智能体强化学习算法不在适用, 因此研究能用于参数化动作空间的多智能体强化学习算法具有重要的现实意义. 提出一种面向参数化动作空间的多智能体中心化策略梯度分解算法, 利用中心化策略梯度分解算法保证多智能体的有效协同, 结合参数化深度确定性策略梯度算法中双头策略输出实现对参数化动作空间的有效耦合. 通过在Hybrid Predator-Prey场景中不同参数设置下的实验结果表明该算法在经典的多智能体参数化动作空间协作任务上具有良好的性能. 此外, 在多巡航导弹协同突防场景中进行算法效能验证, 实验结果表明该算法在多巡航导弹突防这类具有高动态、行为复杂化的协同任务中有效性和可行性.

• 基于预训练模型的用户评分预测

  强敏杰，王中卿，周国栋

  随着商家评论网站的快速发展, 推荐系统所带来的效率提升使得评分预测成为近年来新兴研究任务之一. 现有的评分预测方法通常局限于协同过滤算法以及各类神经网络模型, 并没有充分利用目前预训练模型提前学习的丰富的语义知识. 针对此问题, 提出一种基于预训练语言模型的个性化评分预测方法, 其通过分析用户和商家的历史评论, 为用户在消费前提供评分预测作为参考. 该方法首先设计一项预训练任务, 让模型学习捕捉文本中的关键信息. 其次, 通过细粒度情感分析方法对评论文本进行处理, 从而获取评论文本中的属性词. 接下来, 设计一个属性词嵌入层将上述外部领域知识融入模型中. 最后, 采用基于注意力机制的信息融合策略, 将输入文本的全局和局部语义信息进行融合. 实验结果表明, 该方法相较于基准模型, 在两个自动评价指标上均取得显著的提升.

• 基于半监督学习的长尾时序动作检测

  王雨虹，武港山，王利民

  现实世界中的数据标签分布往往呈现长尾效应, 即少部分类别占据绝大多数样本, 时序动作检测问题也不例外. 现有的时序动作检测方法往往缺乏对少样本类别的关注, 即充分建模样本数量多的头部类别, 而忽视了样本数量少的尾部类别. 对长尾时序动作检测问题进行了系统的定义, 并针对长尾时序动作检测问题, 提出一种基于半监督学习的加权类别重平衡自训练方法, 充分利用现实世界中存在的大规模无标签数据, 来重平衡训练样本中的标签分布, 改善模型对尾部类别的拟合效果. 还针对时序动作检测任务, 提出一种伪标签损失加权方法, 使模型训练更加稳定. 在THUMOS14和HACS Segments数据集上进行实验, 并分别利用THUMOS15数据集和ActivityNet1.3数据集中的视频样本来构成相应的无标签数据集. 此外, 还针对视频审核应用需求, 收集Dance数据集, 包括35个动作类别、6632个有标签视频和13264个无标签视频, 并保留数据分布显著的长尾效应. 使用多种基线模型, 在 THUMOS14、HACS Segments 和 Dance 数据集上进行实验. 实验结果表明, 所提出的加权类别重平衡自训练方法可以提高模型对尾部动作类别的检测效果, 并且能应用于不同的基线时序动作检测模型提升其性能.

• 大语言模型驱动的跨领域属性级情感分析

  李诗晨，王中卿，周国栋

  属性级情感分析作为一种细粒度情感分析方法, 目前在许多应用场景中都具有重要作用. 然而, 随着社交媒体和在线评论的日益广泛以及各类新兴领域的出现, 使得跨领域属性级情感分析面临着标签数据不足以及源领域与目标领域文本分布差异等挑战. 目前已有许多数据增强方法试图解决这些问题, 但现有方法生成的文本仍存在语义不连贯、结构单一以及特征与源领域过于趋同等问题. 为了克服这些问题, 提出一种基于大语言模型(large language model, LLM)数据增强的跨领域属性级情感分析方法. 所提方法利用大模型丰富的语言知识, 合理构建针对跨领域属性级别情感分析任务的引导语句, 挖掘目标领域与源领域相似文本, 通过上下文学习的方式, 使用领域关联关键词引导LLM生成目标领域有标签文本数据, 用以解决目标领域数据缺乏以及领域特异性问题, 从而有效提高跨领域属性级情感分析的准确性和鲁棒性. 所提方法在多个真实数据集中进行实验, 实验结果表明, 该方法可以有效提升基线模型在跨领域属性级情感分析中的表现.

• RobustSketch: 支持网络流量抖动的大流弹性识别方法

  熊兵，刘永青，夏卓群，赵宝康，张锦

  大流识别是网络测量中的一项关键基础性工作, 目前主流的方法是采用概要型数据结构Sketch快速统计网络流量, 进而高效筛选大流. 然而, 当网络流量发生抖动时, 大量分组的急速涌入将导致大流识别精度显著下降. 对此, 提出一种支持流量抖动的网络大流弹性识别方法RobustSketch. 所提方法首先设计基于Sketch循环链的可伸缩小流过滤器, 根据实时分组到达速率适应性扩增与缩减其中的Sketch数量, 以始终完整记录当前时间周期内所有到达的网络分组, 从而确保网络流量抖动出现时仍能精确过滤小流. 然后设计基于动态分段哈希的可拓展大流记录表, 根据小流过滤器筛选后的候选大流数量适应性增加与减少分段, 以完整记录所有候选大流, 并保持较高的存储空间利用率. 进一步, 通过理论分析给出了所提小流过滤器和大流记录表的误差界限. 最后, 借助真实网络流量样本, 对所提大流识别方法RobustSketch进行实验评估. 实验结果表明: 所提方法的大流识别精确率明显高于现有方法, 即使在网络流量抖动时仍能稳定保持在99%以上, 而平均相对误差减少了86%以上, 有效提升了大流识别的精确性和鲁棒性.

• 基于最短路径序列化图的域内路由保护算法

  耿海军，胡睿乾，胡治国，尹霞

  互联网服务提供商采用路由保护算法来满足实时性、低时延和高可用应用的需求. 然而已有路由保护算法存在下面3个方面的问题: (1)在不改变传统路由协议转发机制的前提下, 故障保护率普遍较低; (2)为了追求较高的故障保护率, 通常需要改变传统路由协议的转发机制, 实际部署难度较大; (3)无法同时利用最优下一跳和备份下一跳, 从而导致网络负载均衡能力较差. 针对上述3个问题, 提出一种基于最短路径序列化图的路由保护算法, 所提算法不需要改变转发机制, 支持增量部署, 同时使用最优下一跳和备份下一跳不会出现路由环路, 并且具有较高的故障保护率. 所提算法主要包括下面两个步骤: (1)为每个节点计算一个序号, 构造最短路径正序化图; (2)利用最短路径正序化图和反序搜索规则构造最短路径序列化图, 在此基础上根据备份下一跳计算规则计算节点对之间的备份下一跳集合. 在真实和模拟网络拓扑上进行测试, 实验结果表明, 与其他路由保护算法相比, 所提算法在平均备份下一跳数量、故障保护率和路径拉伸度3个指标方面均具有显著的优势.

• 标准模型下效率更高的身份基匹配加密

  陈洁，楚乔涵，杜秋妍，高莹

  身份基匹配加密是一种新型的密码学原语, 允许接收者与发送者双方都可以指定对方的身份, 只有身份匹配时才可与之通信. 这项加密技术提供了一种非交互式的秘密握手协议以摆脱实时互动, 进一步提高参与者的隐私性. 在标准模型下基于SXDH假设, 提出素数阶群上的身份基匹配加密方案, 实现短参数, 降低解密时的配对次数, 是目前效率最高的身份基匹配加密方案. 此外, 还提出第1个标准模型下基于SXDH假设的等值策略的内积匹配加密方案. 技术路线如下, 首先构造合数阶群上的方案, 然后通过DPVS技术将方案模拟到素数阶群中, 并降低所需的对偶基维数, 进一步减小参数大小. 最后, 替换身份基匹配加密的第1层策略, 构造出等值策略的内积匹配加密方案.

• 基于注意力机制的联邦无线流量预测模型

  柴宝宝，董安明，王桂娟，韩玉冰，李浩，禹继国

  移动数据每天都在不断增长, 如何精准预测无线流量对高效、合理的配置通信和网络资源至关重要. 现有的流量预测方法多采用集中式训练架构, 涉及大规模的流量数据传输, 会导致用户隐私泄露等安全问题. 联邦学习可以在数据本地存储的前提下训练一个全局模型, 保护用户隐私, 有效减轻数据频繁传输负担. 但是在无线流量预测中, 单个基站数据量有限, 且不同基站流量数据模式异构, 流量模式难以捕捉, 导致训练得到的全局模型泛化能力较差. 此外, 传统联邦学习方法在进行模型聚合时采用简单平均, 忽略了客体贡献差异, 进一步导致全局模型性能下降. 针对上述问题, 提出一种基于注意力的“类内平均, 类间注意力”联邦无线流量预测模型, 该模型根据基站的流量数据进行聚类, 更好地捕捉具有相似流量模式基站的流量变化特性; 同时, 设计一个预热模型, 利用少量基站数据缓解数据异构, 提高全局模型的泛化能力; 在模型聚合阶段引入注意力机制, 量化不同客体对全局模型的贡献, 并在模型迭代过程中融入预热模型, 大幅提升模型的预测精度. 在两个真实数据集(Milano和Trento)上进行大量实验, 结果表明该方法优于所有基线方法. 并且与目前最先进的方法相比, 在两个数据集上的平均绝对误差性能增益最高分别达到10.1%和9.6%.

• 意图驱动的网络流量分布式测量方法

  张宇鑫，李福亮，元禹博，王兴伟

  可编程交换机的网络流量测量技术凭借其特性可以处理高速网络流量, 在灵活性、实时性等方面均有巨大的优势. 然而, 由于需要使用复杂的P4语言配置交换机的内部逻辑, 测量任务部署复杂且易错. 此外, 测量准确度往往受限于交换机内部可用的测量资源. 详细研究基于意图的网络及网络流量测量技术, 提出一种意图驱动的网络流量分布式测量方法. 首先, 设计基于测量意图原语的意图表示形式, 构建意图编译器将抽象意图表示转译为可执行的P4代码. 其次, 提出网络流量分布式测量方法, 使用多台交换机的资源以分布式的方式协同完成一个测量任务, 以大流测量为例介绍测量资源动态分配及计数器配置算法. 最后, 实验结果表明所提出的方法可行并且具有一定的优越性.

• 素阶数域上的高效紧凑NTRU密钥封装方案

  梁志闯，赵旭阳，方博越，赵运磊

  基于格(特别是NTRU格)设计后量子密钥封装方案是格密码领域的主流方向之一. 现有多数格密码方案基于分圆环构造, 但分圆环饱含丰富的代数结构导致这些方案容易遭受相关攻击. 一个可选的且更安全的代数结构是大Galois群、素数阶、基于素理想的数域(简称为素阶数域). NTRU-Prime是一个基于素阶数域的备受青睐的NTRU密钥封装方案, 且早已经在国际标准OpenSSH中默认应用. 旨在设计出比NTRU-Prime性能更优的素阶数域上NTRU密钥封装方案. 首先, 梳理分圆环的安全隐患, 特别是针对2次幂分圆环的系列攻击, 同时展示出素阶数域在抵御这些攻击方面的安全优势. 接着, 基于素阶数域提出NTRU密钥封装方案CNTR-Prime, 并给出详细的相关分析和参数集. 然后, 提出一种伪梅森数不完整NTT, 它能有效计算CNTR-Prime中关于素阶数域的多项式乘法. 此外, 还提出一种改进的伪梅森数约减算法, 并将它应用在伪梅森数不完整NTT中. 它在软件实现方面比Barrett约减快2.6%, 在硬件实现方面比Montgomery约减和Barrett约减快2–6倍. 最后, 提供CNTR-Prime的C语言实现, 并与其他同类方案进行全面对比. 结果表明, 与SNTRU-Prime相比, CNTR-Prime在安全强度、带宽和实现效率上有优势, 其中CNTR-Prime-761的经典和量子安全强度都比SNTRU-Prime-761的高19 bit, 密文尺寸降低8.3%, 密钥生成算法、密钥封装算法和解封装算法分别快25.3倍、10.8倍和2.0倍. 实际上, CNTR-Prime-653的经典和量子安全强度已可与SNTRU-Prime-761相媲美, 且CNTR-Prime-653的带宽降低13.8%, 密钥生成算法、密钥封装算法和解封装算法分别快33.9倍、12.6倍和2.3倍. 所提工作可为后续同类型的格密码方案的设计、分析和优化实现提供重要参考.

• 素阶数域上的高效格基数字签名方案

  董怡帆，方博越，梁志闯，赵运磊

  随着量子计算的快速发展, 特别是Shor量子算法及其变体的优化进步, 当前基于大整数分解和离散对数问题的经典公钥密码体制将面临颠覆性的影响. 为了应对量子攻击, 学界开始对后量子密码学的研究, 其中基于格的后量子密码方案因其在安全、效率、带宽等方面的均衡表现和良好的可扩展性而成为后量子密码的主流技术路线. 目前, 基于格的后量子密码方案大多使用分圆环, 尤其是二次幂分圆环作为底层代数结构. 但分圆环中具有丰富的子域、自同构、环同态等代数结构, 容易遭受针对性攻击. 基于具有“高安全性、素数阶、大Galois群和惰性模数”特点的素阶数域, 设计出后量子数字签名方案Dilithium-Prime, 并给出推荐参数集. 然而, 素阶数域的一个显著缺点是无法直接使用快速数论变换(NTT)算法进行高效的多项式乘法, 导致素阶数域上的密码方案性能较差. 为此, 设计素阶数域上的NTT算法和小多项式乘法, 实现素阶数域上高效的多项式乘法. 最后, 为方案的关键算法设计常数时间无分支实现方法, 给出方案的C语言实现, 并与其他方案进行对比. 实验结果表明, 在同一安全等级下, 与分圆环上的数字签名方案CRYSTALS-Dilithium推荐参数相比, Dilithium-Prime方案的公钥尺寸、私钥尺寸、签名尺寸分别降低1.8%、10.2%、1.8%, 签名算法效率提高11.9%, 密钥生成算法、验证算法所需时间分别为CRYSTALS-Dilithium方案的2.0倍和2.5倍, 但不同于CRYSTALS-Dilithium, Dilithium-Prime方案具有抵抗针对分圆环的密码攻击的优越特性; 与2023年韩国后量子密码算法竞赛中提出的基于素阶数域的签名方案NCC-Sign推荐参数相比, 在相同的安全等级和带宽条件下, Dilithium-Prime方案的密钥生成算法、签名算法、验证算法的速度分别提升至4.2倍、35.3倍、7.2倍, 实现兼顾高效性和安全性的素阶数域签名算法.

• LazyStore: 基于混合存储架构的写优化键值存储系统

  杜云箫，陈珂，寿黎但，江大伟，骆歆远，陈刚

  基于日志合并树(LSM-tree)的键值(key-value)存储由于其出色的读写性能而被广泛用于许多应用中. 大多数现有的日志合并树采用多层结构来存储数据. 尽管多层数据结构可以很好地服务于适度的写密集型应用, 但这种结构并不十分适合高写密集型应用. 这是因为以多层方式保存数据会引入写放大问题, 即新的数据插入会引发很大一部分已经存储在多层中的数据被重组的问题. 这种巨大的(有时是频繁的)数据重组是昂贵的, 并且在许多高写密集型的应用中降低了写入性能. 此外, 多层结构不能为热数据持续提供出色的读取性能. 这是因为多级结构不能通过及时合并重叠的范围来优化热数据的读取操作. 为了解决上述两个问题, 提出LazyStore, 一种基于混合存储架构的新型单层日志合并树. LazyStore通过将数据存储在单一逻辑层而不是多个逻辑层来解决写放大的问题. 因此, 昂贵的多级数据重组在很大程度上被消除. 为了进一步提高写入性能, LazyStore根据每个存储设备的容量和读/写性能, 将逻辑层中的数据分布到多个存储设备中, 如内存、非易失性内存和闪存. 此外, LazyStore引入实时合并操作, 以提高热数据范围的读取性能. 实验表明, 与其他多级日志合并树相比, LazyStore最多将写入性能提高3倍, 并将写入放大率降低至1/4. 而对于热门范围的读取, LazyStore的实时数据合并优化可以将范围查询处理的延迟降低一半.

• 基于本地化差分隐私的多表星形连接查询

  张啸剑，曹小杰，王宁，孟小峰

  基于本地化差分隐私多关系表示上的Star-JOIN查询已得到研究者广泛关注. 现有基于OLH机制与层次树结构的Star-JOIN查询算法存在根节点泄露隐私风险、τ-截断机制没有给出如何选择合适τ值等问题. 针对现有算法存在的不足, 提出一种有效且满足本地化差分隐私的Star-JOIN查询算法LPRR-JOIN (longitudinal path random response for join). 该算法充分利用层次树的纵向路径结构与GRR机制, 设计一种纵向本地扰动算法LPRR, 该算法以所有属性纵向路径上的节点组合作为扰动值域. 每个用户把自身元组映射到相应节点组合中, 再利用GRR机制对映射后的元组进行本地扰动. 为了避免事实表上存在的频率攻击, LPRR-JOIN算法允许每个用户利用阈值τ本地截断自身元组个数, 大于τ条元组删减、小于τ条元组补充. 为了寻找合适的τ值, LPRR-JOIN算法利用τ-截断带来的偏差与扰动方差构造总体误差函数, 通过优化误差目标函数获得τ值; 其次结合用户分组策略获得τ值的总体分布, 再利用中位数获得合适的τ值. LPRR-JOIN算法与现有算法在3种多关系数据集上进行比较, 实验结果表明其响应查询算法优于同类算法.

• 基于密度的多度量空间数据聚类算法

  朱轶凡，罗程阳，马瑞遥，陈璐，毛玉仁，高云君

  具有噪声的基于密度的数据聚类(DBSCAN)算法是数据挖掘领域中的经典方法之一, 其不仅能发现数据中潜藏的复杂关系, 还能过滤其中的数据噪声, 从而获得高质量的数据聚类. 然而, 现有的基于密度的数据聚类算法仅支持单模态(类型)数据的聚类, 难以应对多模态(类型)数据并存的应用场景. 随着信息技术的快速发展, 数据呈现多模态化的发展态势, 现实生活中的数据不再是单一的数据类型, 而是多种数据模态(类型)的组合, 如文本、图像、地理坐标、数据特征等. 因此, 现有的数据聚类方法难以对复杂的多模态数据进行有效的数据建模, 更无法进行高效的多模态数据聚类. 基于此, 提出一种基于密度的多度量空间聚类算法. 首先, 为了刻画多模态数据间的复杂关系, 利用多度量空间表征数据之间的相似性关系, 并且利用聚合多度量图索引(AMG)实现多模态数据建模. 接着, 利用差分化的相似性关系优化聚合多度量图的图结构, 并且结合最优策略优先的搜索策略进行剪枝, 以实现高效的多模态数据聚类. 最后, 在真实与合成数据集上针对多种参数设置进行实验. 实验结果验证了所提方法运行效率提升了至少1个数量级, 并具有较高的聚类精度与良好的可扩展性.

• 运动感知的移动游戏帧率调整算法

  梁宇智，霍宇驰，王锐

  随着移动设备的广泛普及, 其图形处理器的性能也逐渐增强. 为了满足用户对卓越体验的不断追求, 移动设备屏幕分辨率和刷新率每年都在不断提升. 与此同时, 移动游戏中的可编程绘制流水线也变得日益复杂, 这导致游戏应用成为移动设备功耗的主要来源. 研究了移动游戏中的绘制流水线, 提出一种运动感知的绘制帧率调整方法, 以在节能模式下保证绘制质量. 与以往仅考虑历史帧绘制误差的预测模型不同, 该方法通过建立摄像机位姿和帧间绘制误差的非线性关系模型, 通过未来帧新的摄像机位姿预测其绘制误差, 实现更为精确的帧率调整策略. 此外, 该方法还包括一个轻量级的场景识别模块, 可根据玩家所处特定场景有针对性地调整误差阈值, 从而采用不同程度的帧率调整策略. 在定量对比上, 相比只考虑历史帧误差的预测模型, 构建的模型在游戏帧序列上的预测准确性提高30%以上. 同时, 在用户实验的定性对比上, 相同跳帧比例下该方法能够得到用户体验更好的绘制效果. 提出的算法融合了历史帧误差和摄像机位姿变化信息, 能够预测出更准确的未来帧误差. 算法结合预测结果和场景识别结果, 实现了更好的动态帧率调整效果.

• 无监督多视图特征选择研究进展

  吴建生，李艳兰，黄冲，闵卫东

  多视图数据从不同角度描述数据对象, 数据在不同视图中的特征表示之间存在着相关性、互补性及多样性信息. 综合利用这些信息对多视图数据处理至关重要. 然而, 多视图数据通常具有高维度特点, 且常含有噪声特征, 这为多视图数据的处理与分析带来了许多困难. 无监督多视图特征选择无需样本标记信息, 从多个视图源的原始高维特征中学习更紧凑、更准确的特征表示以提高数据分析的效果, 在多视图数据处理领域起着重要作用. 根据已有的无监督多视图特征选择模型的工作机制的异同, 对这些模型进行归纳和总结, 分析其中存在的不足, 并指出未来研究的方向.

• HchMER: 混合人机智能的手写数学表达式识别方法

  康文惠，黄进，仝青山，付强，田丰，戴国忠

  随着人工智能和端到端识别方法在手写数学表达式识别上的应用, 数学表达式识别准确率有了明显的提高. 然而, 与公开数据集上的测试不同, 实际应用中人的参与为识别算法引入了更多的不确定因素, 如个性化的笔画信息、包含歧义的手写字符, 以及不确定的公式结构等, 影响了识别算法的性能. 为此, 提出了一种混合人机智能的手写数学表达式识别方法HchMER. 该方法借助手写数学公式识别算法、知识库和用户反馈, 增强机器对用户输入的数学表达式的理解, 从而提升手写数学表达式的编辑速度和准确率. 为了验证HchMER的有效性, 将其分别与MyScript Math Recognition (MyScript)算法, 以及一个成熟的商用产品“Microsoft Ink Equation” (InkEquation)进行了比较. 实验结果表明, HchMER在准确率上较MyScript和InkEquation分别提高了23.2%和26.51%. 在平均完成时间上, HchMER比MyScript增加了44.46% (9.6 s), 但是比InkEquation降低了11.48% (4.05 s). 同时, 被试在问卷调查和半结构化访谈中对HchMER给予了肯定.