计算机科学与探索

当前目录

• 基于XACML的策略冲突检测与消解方法

  王聪，李瑞轩，辜希武，汤俊伟

  基于XACML（extensible access control markup language）的访问控制策略在云计算服务中得到广泛使用，其存在的问题也日益凸显，策略集的冲突检测与冲突消解问题就是其中之一。然而，目前学术界在冲突消解方面研究较少，现有的研究也仅能对冲突进行逐对消解，没有针对大量冲突的一次性消解方法，这在大规模云计算环境中是很难适用的。针对这个问题，从算法的角度出发，改进了原有的策略冲突检测方法，并设计了一种新的策略冲突一次性消解算法。该算法将安全规则映射到[N]维空间中，每一个维度表示一个属性，将定义复杂的安全策略在每一个属性上统一表示为几种基本数据类型的属性值集合，通过对简单集合的交集运算来进行冲突和冗余检测。在冲突消解时，将所有的冲突汇集到一起，运用有向无环图的拓扑排序来计算规则优先级，按优先级的顺序为每个规则构建一棵空间区域选择树，选取其对应的消解后的[N]维空间区域，完成大量冲突的一次性消解。实验表明，冲突检测和一次性消解算法是正确、高效和可行的。

• 高效命名数据网卫星视频直播方法

  杨亚龙，嵩天，朱洪辰

  视频直播实时性强，应用广泛，是视频服务中的一种特殊应用。基于命名数据网络（named data networking，NDN）而非传统端到端的TCP/IP体系结构提供网络视频直播，并通过卫星广播进行内容分发，可以以相对较低的通信开销提供大范围高质量服务。然而，由于卫星链路传播延迟较高，基于NDN的卫星广播视频直播应用在内容分发过程中会出现冗余数据传输（redundant data transmission，RDT）现象。RDT将造成卫星链路通信计算资源的浪费，影响应用效率。为了解决该问题，进一步提升应用效率，在NDN的基础上进行改进，提出了容迟未决信息表（delay pending interest table，DPIT）。实验结果表明，DPIT可以有效降低RDT问题造成的影响，提升基于NDN组网卫星的广播视频直播应用效率。

• 空间位置约束下的三维音频对象参数动态量化

  李雪哲，王晓晨，高丽，涂卫平，柯善发

  近年来，在某些交互场景中，面向对象空间音频编码能够允许用户更加灵活地对特定对象进行个性化的渲染和重组。然而，如果对象音频分别编码会导致整体码率随着对象数目的增加而同步大幅增加。MPEG组织提出的面向对象音频编码（spatial audio object coding，SAOC）可以将所有对象下混成一个单独的混合信号，同时为每个对象提取少量的边信息。但是，当其对超过32个对象音频进行编码时，边信息的码率会随着对象数目的增加而增大，甚至会远大于下混对象的码率。为了解决这个问题，提出一种在面向对象编码中基于空间位置约束的空间参数动态量化方法，以叠加定位原理为理论基础，利用虚拟声源的空间位置与产生该声源的音频对象的空间位置之间的约束关系，确定出空间约束区域以及局部空间量化码本，并针对提取出的虚拟声源的空间方位，进行空间参数的量化编码。最后给出主观实验和客观实验，表明在音质和空间方位大致相当的情况下，边信息的码率比SAOC方法降低约30%。

• 数据平台的设计和实现以及大赛中的应用

  王永坤，金耀辉

  得益于大数据相关的开源软件蓬勃发展，中小企业和机构也可以进行大数据平台的搭建和应用。但是数据平台在实际应用中仍然有很多挑战，例如如何进行开放数据的共享和计算，并保证代码安全等。基于开源软件设计了一个数据平台架构来让用户一站式地共享数据和计算，同时跟踪和审核代码。根据此设计搭建了一个生产环境，并给出了基本的测试来验证平台的可用性。把平台开放给外界使用，成功地支持了上海开放数据创新应用大赛（Shanghai Open Data Apps，SODA）中的大量用户的数据共享和计算需求。

• 面向不确定文本数据的余弦相似性查询方法

  朱命冬，徐立新，申德荣，寇月，聂铁铮

  最近邻查询在多个领域具有广泛的应用，如组合过滤、基于位置的服务、决策支持系统等。而且随着Web信息实体抽取、隐私保护信息转化、图像识别等技术的发展和普及，在诸多领域，不确定性文本数据普遍存在，基于信息论的TF-IDF算法，可以将文本型的相似匹配转化为数值型的向量的计算，具有严密性和有效性。但TF-IDF信息的余弦距离不属于度量空间，难于构建索引。为此主要研究了面向不确定文本数据基于余弦相似度的相似性查询方法。通过分析不确定性余弦相似度计算的特性，提出了快速相似度计算方法。通过对余弦距离的计算进行转换，构建改进的索引结构sMVP-tree（statistic multiple vantage point tree），并给出了基于余弦相似度面向不确定性数据的相似度计算方法。最后，结合该相似度计算方法提出了分布式环境下[kNN]查询和[RkNN]查询算法。大量的基于真实数据的实验验证了算法的正确性和有效性。

• 并行广义本征值求解器GenELPA

  沈瑜，孙广中

  高效率的大规模并行求解广义本征值方程是在计算电子结构等高性能计算学科中的一个重要课题，在未来E级计算的发展上有重要的意义。根据马普研究所近几年开发的一种面向P级应用的本征值求解库（eigenvalue solver for petaflop-applications，ELPA），针对广义本征值问题，开发了一款开源并行广义本征值求解器GenELPA，实现了从广义本征值问题到一般本征值问题的转换方法，避免了潜在的问题；然后调用ELPA进行计算，具有良好的计算速度和并行效率；同时采用了类似ScaLAPACK的接口，更加易于使用。在第一性原理软件ABACUS（atomic-orbital based ab-initio computation at USTC）中的实际应用表明该求解器具有理想的计算速度提升。

• Map/Reduce下快速剪枝算法在复杂任务调度中的应用

  裴树军，宋冬梅，孔德凯

  云环境下传统任务分配与调度算法对于复杂任务调度的整体效率较低，为了提高Map/Reduce对复杂任务分配调度的整体效率，提出了一种基于任务处理时间的快速剪枝算法。该算法首先将复杂任务按照任务依赖关系大小进行最佳拓扑排序，使任务按顺序执行，从而提高调度准确率。然后使用节点处理任务的预测时间与节点处理能力的比值作为子任务在每个节点的处理时间进行量化建模，建立任务和处理时间的度量矩阵，通过采用按阶剪枝方法逐渐缩小任务分配规模，对N个节点处理N个任务的分配问题，进行N-1次操作可获得任务分配的最优解。运用Hadoop平台进行实验验证，从任务调度效率与资源使用率角度将剪枝算法与公平调度算法、遗传算法和GRAPHENE算法进行对比验证。实验结果表明剪枝算法能明显提高任务调度的整体效率，充分利用各节点的计算能力提高Map/Reduce调度效率。

• 社交关系在基于模型社会化推荐系统中的影响

  房倩琦，柳玲，文俊浩，曾骏，高旻

  目前社会化推荐系统方面的研究主要集中于构建性能更优的基于模型的推荐算法，然而模型算法中分解得到的隐式特征和社交信息的变化会给推荐性能带来不确定性。为了消除不确定性，探究了在基于模型的社会化推荐系统中社交关系的变化对推荐性能的影响。实验首先按比例移除关系网络中的连边或节点，再对推荐质量进行评估，结果表明，社交关系的数量增多将对推荐质量带来明显提升，同时关系网络中心节点对推荐质量的影响巨大。因此，在构建基于模型的社会化推荐系统的过程中应尽可能多地获取社交关系，并提升中心节点的关系在推荐中的权重，降低非中心节点（潜在噪声）的影响。

• 融合“用户-项目-用户兴趣标签图”的协同好友推荐算法

  陈洁敏，李建国，汤非易，汤庸，陈笑凡，唐婷芳

  随着社交网络的用户数量呈爆炸式增长，如何为用户推荐具有相同兴趣爱好的好友已成为当前研究的焦点。为此，提出了一种基于“用户-项目-用户兴趣标签图”的协同好友推荐算法。该算法首先利用基于“用户-项目-标签”的三部图物质扩散推荐算法来计算用户之间的相似度，并引入“用户-用户兴趣标签图”二元关系，通过用户的兴趣标签图来发掘用户的兴趣主题；然后根据用户主题分布，利用KL距离来计算用户之间的相似度；最后将两组结果采用调和平均数方式融合得到用户间的综合相似度，并进行好友的推荐。通过在Delicious和Last.fm数据集上的实验证明，该算法能有效提高Top-N推荐的准确率和召回率，同时通过在学术社交网站——学者网数据集上进行的学者推荐实验表明，该算法能有效提高核心用户的推荐度。

• Web应用程序异步请求时序问题检测

  吉华斌，尚颖，李征

  AJAX（asynchronous JavaScript and XML）技术广泛应用于Web应用程序，实现了异步发送请求。在异步请求过程中，由于程序代码设计不合理和网络延迟等原因，会引发异步请求错误。目前的研究提出了静态和动态的分析方法检测AJAX错误，然而忽略了返回数据中包含可能存在事件操作的异步请求，同样可以引发异步请求错误。在动态分析技术的基础上，通过URL参数从服务器端获取完整的返回数据并解析其中的事件操作，分析事件操作之间或与原有的异步请求之间可能引发的问题，并将此类问题定义为异步请求时序问题；然后将两者一起构成异步请求交错图，通过图的连通关系检测可能发生的异步请求错误；最后在此基础上提出了一个完整的工具原型，用于自动化检测Web应用程序中的异步请求时序问题。利用所提出的方法，针对现有5个特定Web应用程序和5个开源Web应用程序，检测异步请求中的三类问题，并通过控制网络条件进行验证，结果表明了该检测方法的有效性，与之前的方法相比，该方法能够实现更多的Web应用程序问题检测。