计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2016年第10期杂志 文档列表

计算机学报杂志数据科学与工程

大数据环境下支持概率数据范围查询索引的研究1929-1946

摘要：随着数据规模的不断增长,大数据管理具有重要意义.在众多数学模型中,因为概率模型可以将海量数据抽象成少量概率数据,所以它非常适合管理大数据.因此,研究大数据环境下的概率数据管理具有重要意义.作为一种经典查询,基于概率数据的范围查询已被深入研究.然而,当前研究成果不适合在大数据环境下使用.其根本原因是这些索引的更新代价较大.该文提出了索引HGD-Tree解决这一问题.首先,该文提出了一系列算法降低新增数据的处理代价.它可以保证树结构平衡的前提下快速地执行插入、删除、更新等操作.其次,该文提出了一种基于划分的方法构建概率对象的概要信息.它可以根据概率密度函数的特点自适应地执行划分.此外,由于作者提出的概要是基于比特向量,上述策略可以保证索引以较低空间代价管理概率数据.最后,该文提出了一种基于位运算的方法访问HGD-Tree.它可以用少量的位运算执行过滤操作.大量的实验验证了算法的有效性.

一种大规模网络中基于节点结构特征映射的链接预测方法1947-1964

摘要：网络链接预测能够获取网络中丢失链接的重要信息或进行网络的动态演变分析.现有的基于节点相似性的网络链接预测方法往往针对简单的一（多）阶邻居信息或特定类型的小型网络,设计较为复杂的计算方法,其扩展性和大规模网络中的可计算性都受到了严峻的挑战.文中基于深度学习在神经网络语言模型中应用的启发,提出了一个LsNet2Vec（Large-scale Network to Vector）模型.通过结合随机游走的网络数据集序列化方法,进行大规模的无监督机器学习,从而将网络中节点的结构特征信息映射到一个连续的、固定维度的实数向量.然后,使用学习到的节点结构特征向量,就可以迅速计算大规模网络中任意节点之间的相似度,以此来进行网络中的链接预测.通过在16个大规模真实数据集上和目前的多个基准的最优预测算法对比发现,LsNet2Vec模型所得到的预测总体效果是最优的：在保证了大规模网络中链接预测计算可行性的同时,于多个数据集上相对已有方法呈现出较大的AUC值提升,最高达8.9%.

一种基于Sketch的Top-k紧密中心性快速搜索算法1965-1978

摘要：在大数据的时代背景下,由于网络数据（network data）能有效简洁地描述社交网络、电子商务、医疗记录、在线教育等多种应用中各类复杂关系,越来越受到工业界和学术界的关注.在社交网络分析任务中,一个基本操作是从网络中发现重要程度前k大的节点.紧密中心性（closeness centrality）是一种常见的节点重要性刻画指标,它用节点在网络中心的程度来反映节点的重要性.用紧密中心性衡量节点重要性进行节点搜索的问题称为top-k紧密中心性搜索问题.然而,传统的精确算法由于其多项式级别的复杂度无法高效地扩展到大规模的网络数据上.近来,研究人员提出了近似算法,通过牺牲结果精度来获得性能提升.通过分析发现,目前存在的近似算法虽然性能得到了有效提升,但是结果精度牺牲过大.为了解决这个问题,该文设计了一种新颖的近似算法,叫做基于Sketch的紧密中心性搜索算法.此近似算法应用了一个全新的计算方式,利用Sketch估计同一距离的邻居数目,然后得到近似的最短距离之和,最终得到各个节点的紧密中心性的估计值.此算法的时间复杂度为O（mtDmax）,其中t是常数,Dmax是网络直径,m是网络边数.根据实际社交网络的小世界现象的特性,此近似算法基本是个线性算法.最后,相比于目前存在的精确算法和近似算法,该文通过全面的实验验证了基于Sketch的紧密中心性搜索算法在时间性能和结果精度等两方面的优势.

免预设间隔约束的对比序列模式高效挖掘1979-1991

摘要：对比序列模式在识别不同类别序列样本集合的特征上有着重要的作用.已有对比序列模式挖掘算法需要用户预设间隔约束.在不具备充分先验知识情况下,用户不易准确地预设恰当的间隔约束,进而导致不能发现有用的模式.对此,文中设计了带紧凑间隔约束的最小对比序列模式挖掘算法,实现免预设间隔约束,并对候选模式自动计算最适合的间隔约束.此外,设计了3种剪枝策略来提高算法的执行效率.通过蛋白质序列、DNA序列、行为序列数据集验证了提出的算法的有效性和高效率.

基于用户行为特征的微博转发预测研究1992-2006

摘要：微博转发预测对微博话题检测和微博影响力评估具有重要意义,引起了学界和产业界的广泛关注.现有方法主要集中在微博属性及微博传播网络特征的研究,没有充分考虑转发行为的动态性和用户历史行为的规律性.文中从微博能见度和用户行为特征角度研究微博转发预测问题,（1）提出了基于用户活跃期和时间窗的转发行为、忽略行为、未接收行为识别方法,为模型训练和效果分析提供了更为准确的数据基础;（2）提出了基于时间衰减的用户兴趣计算模型,有效度量用户兴趣及其变化特性对用户转发行为的影响程度;（3）提出了用户转发率、交互频率等用户行为特征,有效度量了用户历史行为模式和用户影响力传递效应的差异性对用户转发行为的影响,最后融合上游用户特征、微博特征、转发用户兴趣和历史行为特征,提出了基于分类模型的转发行为预测方法.在真实数据上的实验结果表明,该方法能够有效提升预测准确性,并且能够在较小规模的训练集上取得好的预测效果.

数据流上动态轮廓查询处理技术的研究2007-2030

摘要：轮廓查询（Skyline）是一种典型的多目标优化问题.动态轮廓查询（Dynamic Skyline）是轮廓查询的一个重要变种,其目标是对于一个给定的查询点q,返回在各维度上最接近q的所有点.对比轮廓查询,动态轮廓查询根据查询点q的位置变动,可以更加灵活地返回查询结果.文中关注数据流上动态轮廓查询处理,此问题在多目标决策方面具有非常重要的应用.为有效地解决该问题,首先提出了一种组合式索引结构来管理数据流上的点,该索引结构包括两个部分：对整体数据使用分层次划分结构进行维护;对子划分内部数据采用倒排索引结构进行维护.该组合式索引结构具有更新快、过滤性能高、适合任意数据分布等优点,可以提高动态轮廓的查询处理效率.然后,基于该组合式索引结构,提出了基础的数据流上动态轮廓查询算法（Basic Dynamic Skyline Query over Data Stream,BDS2）.通过维护少量的数据,BDS2可以快速地计算出数据流上的动态轮廓集合.然而BDS2在处理个别更新时,会有较大的时间延迟,为了更稳定地计算数据流上的动态轮廓,避免更新某些点时计算量急剧增加,进一步提出了改进的数据流上动态轮廓查询算法（Improved Dynamic Skyline Query over Data Stream,IDS2）.最后,通过一系列的实验验证了文中所提出算法的有效性.

基于词汇时间分布的微博查询扩展2031-2044

摘要：该文提出了一种面向微博检索的基于词汇时间分布的查询扩展方法.该方法利用扩展词与查询词的时间分布的相似性来度量扩展词与查询词之间的相关度,建立了基于词汇时间分布的查询模型.具体而言,该文在提出词汇时间分布的定义和估计方法的基础上,给出了查询词与扩展词的时间分布相似性的度量,以此作为它们的相关度,完成扩展词的选择和查询模型的重估.该文方法利用时间信息而不是内容来扩展查询,避免了基于内容的查询扩展方法因微博内容短而无法准确估计扩展词的不足.由TREC 2011和TREC 2012微博检索评测数据上的实验结果表明,基于词汇时间分布的查询扩展模型有效地提高了微博检索的性能,不仅显著优于经典的基于内容的查询扩展模型,而且优于其他利用时间进行查询扩展的方法.

基于路网的三维虚拟现实场景间接可视查询框架2045-2060

摘要：针对现有网络环境下的B／S模式下三维虚拟现实场景在加载过程中因加载大量的不可视的对象而引起资源消耗过高、加载速度过慢的问题,文中提出了一种基于路网的可视动态加载框架.该框架对三维虚拟现实场景内的静态对象和动态对象的可视查询分别进行处理.设计了框架内的路网、移动对象、静态对象可视关系表和动态对象可视关系表的数据模型,并给出了可视关系表的维护算法.对于场景内的静态对象的可视查询,给出基于静态对象可视关系表的静态可视查询框架及算法,避免了复杂的在线可视计算;对于场景内的动态对象的可视查询,则给出基于动态对象可视关系表的连续可视范围查询框架及算法.实验结果表明,在保持三维虚拟现实场景观测效果不变的情况下,可视动态加载框架能够大幅度降低虚拟现实场景中的静态和动态对象的加载数据量和更新数据量,降低对于网络带宽和客户端硬件的需求.

基于外存后缀树的top-k局部比对算法2061-2074

摘要：局部比对是一种衡量字符串间相似程度的技术,它在生物信息学领域具有十分重要的作用.介于此,许多学者已对其进行了深入的研究.然而,随着数据规模的扩大,常规的内存算法已不适用于支持大规模文本数据的局部比对.为解决上述问题,该文研究了基于外存后缀树的top-k局部比对算法.它从根本上消除了内存空间对算法的束缚.为了提高算法的性能,该文首先将经典内存算法中的过滤策略引入该文.通过适当的修改,这些策略可以基于外存后缀树有效地降低计算开销.其次,该文提出一种巧妙的算法支持top-k局部比对查询.该算法通过引入启发式策略有效规避了TA算法的固有问题.具体地,它一方面可以提高算法的过滤能力,另一方面可以降低候选对象的维护代价.再次,该文对外存后缀树和磁盘的工作原理进行了研究.基于此,该文提出一种槽的结构支持查询.该结构既可以实现磁盘的顺序访问,又可以降低磁盘的访问次数.因此,它可以有效提高算法的查询效率.最后,大量的实验验证了该文所提出算法的有效性.

基于非主属性值的实体匹配2075-2087

摘要：实体匹配旨在找出不同数据源中指代同一实体的实例.已有的实体匹配方法大都基于实体主属性值的相似度进行匹配,而很少有工作考虑到使用实体的非主属性值来辅助实体匹配.然而,当两条指代同一实体的主属性值差异较大的时候,这两个实体可能不会被认为是匹配的实体.另一方面,这两个实体很可能共享一些特别的非主属性值,而这些非主属性值恰好可以反映出两个实体的匹配关系.基于这种思想,文中提出了一种新颖的基于非主属性值的实体匹配算法.该算法以类似于决策树的结构为基础,通过使用这种结构,不仅可以解决噪声值和空缺值带来的问题,而且可以极大地提高发现匹配记录以及尽可能早地排除不匹配记录的效率.多个数据集上的实验结果表明我们的方法比现有的实体匹配方法具有更高的准确率和召回率.此外,使用我们提出的基于决策树的匹配算法等有关技术较Baseline匹配算法在匹配效率上高出10倍多.

面向维基百科的领域知识演化关系抽取2088-2101

摘要：互联网下同一领域中不同知识概念间存在多种关系,其中演化关系对于用户学习和理解领域知识,梳理领域知识的前序和后续逻辑关系具有重要意义,然而网络数据的多样和无序使用户难以准确有序地获取领域知识关系.针对该问题,提出一种面向中文维基百科领域知识的演化关系抽取方法,利用语法分析特征,挖掘演化关系模式,构建演化关系推理模型,采用基于句子层面的关系抽取算法识别领域知识演化关系,最后在真实的维基百科数据集上对该文方法进行了性能评测.实验表明,该方法具有较高的关系抽取准确率和召回率,能有效地抽取出维基百科中领域知识的演化关系.同时,基于实验抽取结果构建知识图谱,能有效挖掘领域学科下知识集合的演化体系,识别重难点知识,对学科建设以及相关课程教学具有一定的指导意义.

基线与增量数据分离架构下的分布式连接算法2102-2113

摘要：在大数据背景下,数据库系统表连接操作的效率急需优化,尤其对于基线与增量数据分离的数据库系统来说,其连接操作更是成为其性能的主要瓶颈.为了有效提升事务处理的性能,在基线与增量数据分离的数据库系统架构中,通常将基线数据存储于磁盘中,增量数据存储于内存中,进而获得较高的事务处理吞吐量和可扩展性.Hbase、BigTable、OceanBase等系统是典型的基线与增量数据分离的数据库管理系统,但是他们的表连接效率较低,其主要原因包括：每次表连接前必须先合并基线数据和增量数据;数据存储模式更为复杂,导致过大的网络开销.该文提出了一种基线与增量数据分离架构下的排序归并连接优化算法.该算法对连接属性做范围切分,在多个节点上并行做排序归并连接.该算法无需在连接前合并基线数据和增量数据,进而实现对基线和增量数据并行处理,同时也避免了大量非连接结果集数据的基线与增量合并操作.并在开源的数据库OceanBase上实现了该算法,通过一系列实验证明,该算法可以极大提高OceanBase数据库的表连接处理性能.

一种针对社会化导购的橙领推荐方法研究2114-2133

摘要：社交网络和网络购物的发展普及导致了社会化导购的产生和发展,也催生了通过在社交网络中推荐产品从而获取利润的“橙领”.通过对橙领相关技术的研究,能更透彻地了解基于社会网络的产品营销机制以及探索社会化导购的底层模式.目前国内外少有这方面研究.因此,文中针对橙领的自身定位问题和面向用户或商家的橙领推荐问题,提出一种针对社会化导购的橙领推荐方法,主要包括3个算法：橙领定位算法、面向用户的橙领推荐算法OCRA4U（Orange Collar Recommending Algorithm for User）和面向商家的橙领推荐算法OCRA4S（Orange Collar Recommending Algorithm for Shop）.橙领定位算法依据橙领的推荐历史对橙领进行定位特征向量化描述,最终转化为一个聚类问题进行解决.OCRA4U考虑了橙领在社交网络中的影响力和橙领与用户需求的匹配度,得到橙领推荐列表.OCRA4S结合橙领在网络中的影响力以及橙领的历史推荐产品,推荐出最符合商家产品需求的橙领列表.基于新浪微博数据集和DBLP数据集,文中设计并实现了3个相关实验：橙领定位算法实验、橙领推荐实验以及社会化数据影响实验,实验结果验证了所提算法的准确性和可行性.

微函数依赖及其推理2134-2148

摘要：起初,作为一个数据库模式设计的工具,函数依赖理论得到了很多的关注,而在数据修复中,该理论并不是十分有效.近年来,针对不一致数据的检测和修复问题,更多的约束被提出来,包括条件函数依赖、修复规则以及编辑规则等.然而,这些方法都只关注了属性整体之间的依赖关系,而实际应用中的数据通常有属性部分之间的依赖关系.例如,某单位员工的工号前两位决定了其所属的部门,而此类依赖信息就被已有方法忽略.该文首先提出了一类更一般化的约束——微函数依赖,微函数依赖引入提取函数,用来表示属性的部分信息.利用提取函数之间的依赖关系,能够检测出更多的不一致数据.理论方面,该文首先研究了微函数依赖的可满足性问题和蕴含问题,然后提供了一个正确且完备的推理系统.最后,通过实验证实了微函数依赖能够在可接受的时间开销内检测出更多的错误数据.

面向MAX/MIN优化的SQL Window函数处理2149-2160

摘要：Window（窗口）函数作为关系数据库领域中数据分析技术的一种解决方案,其精妙的语义特征使其能代替自连接（Self Join）和相关子查询（Sub Queries）等完成传统复杂查询功能,现已被广泛应用到互联网应用的数据管理和分析中.在目前互联网应用步入大数据时代的背景下,针对高吞吐和实时响应等需求,已有的Window（窗口）函数的处理性能已经出现了瓶颈.文中首先介绍了关系数据库中窗口函数在执行器中的两阶段执行框架,然后基于PostgreSQL数据库中原有MAX/MIN Window（窗口）函数执行框架,提出了一种基于临时窗口的优化方法,来优化SQL Window查询针对MAX/MIN函数的处理,并给出了查询代价的分析模型,从理论上分析了该算法的性能.通过与现有商业数据库SQL Server进行性能上的对比,验证了该方案的有效性.