基于端到端分布式框架的符号网络预测方法

社交网络中的链接关系根据其潜在含义可分为正关系和负关系。若对网络中的链接关系进行正负标注,则可形成一个符号网络。符号网络在社会学、信息学、生物学等多个领域存在广泛应用。针对符号网络中链接关系的正负预测已经成为当前研究的热点之一。在大数据背景下,随着符号网络规模的日益增大,符号预测算法的可伸缩性问题日益突出。一些研究者提出了分布式环境下的符号预测方法,使得算法的可伸缩性问题部分得到缓解。但由于大多数算法采用了服务器-客户端方式的分布式框架,导致问题并没有得到根本上的解决。本文提出了一种新的端到端分布式框架（Client to Client Distributed FrameWork,简称C2CDF）,相比传统服务器-客户端架构的集中通信模式,C2CDF各个节点间地位平等,不存在集中通信,集群的带宽瓶颈和压力大大减轻。通过在社交网络正负符号预测、广告点击率预测及森林类型预测等三个不同真实数据集上的实验证明,C2CDF能够在拥有更高准确性的同时,获得2.3-3.3倍的加速比,而且拥有良好的泛化性,不仅能应用在社交网络正负符号预测方面,也能作用于广告点击预测等其他领域。     

基于向量引用Platform-Oblivious内存连接优化技术

以MapD为代表的图分析数据库系统通过GPU、Phi等新型众核处理器来支持高性能分析处理,在面向复杂数据模式时连接操作仍然是重要的性能瓶颈.近年来,异构处理器逐渐成为高性能计算的主流平台,内存连接性能的研究从多核CPU平台扩展到新兴的众核处理器,但众多的研究成果并未系统地揭示连接算法性能、连接数据集大小、硬件架构之间的内在联系,难以为未来异构处理器平台的数据库提供连接平台优化选择策略.本文以面向多核CPU、Xeon Phi、GPU处理器平台的内存连接优化技术为目标,通过优化内存哈希表设计,实现以向量映射替代哈希映射操作,消除哈希代价对内存连接算法的影响,从而更加准确地测量内存连接算法在多核CPU的cache大小、Xeon Phi的cache大小、Xeon Phi的并发多线程、GPU的SIMT（单指令多线程）机制等硬件相关因素影响下的性能特征.实验结果表明,缓存与并发多线程机制是提高内存连接算法性能的重要影响因素.缓存机制对于满足cache大小的连接操作具有性能优势,而GPU的并发多线程机制则在较大表的连接操作中具有较高的性能,Xeon Phi则在满足其L2 cache大小的连接操作中具有最高性能.实验结果揭示了内存连接操作性能与异构处理器硬件特性的联系,为未来异构处理器平台内存数据库查询优化器提供了优化策略.     

融合主题模型和协同过滤的多样化移动应用推荐

随着移动应用的急速增长,手机助手等移动应用获取平台也面临着信息过载的问题.面对大量的移动应用,用户很难找到想到的或适合的应用,而另一方面长尾应用淹没在资源池中不被人所知.已有推荐方法多注重推荐准确率,忽视多样性,推荐结果中多是下载量高的应用,使得推荐系统的数据积累越来越偏向于热门应用,导致长期的推荐效果越来越差.针对此问题,本文首先改进了两个推荐方法,提出了将用户的主题模型和应用的主题模型与MF相结合的LDA_MF模型,以及将应用的标签信息和用户行为数据同时加以考虑的LDA_CF算法.为了结合不同算法的优点,在保证推荐准确率的条件下提升推荐结果的多样性,我们提出了融合LDA_MF、LDA_CF以及经典的基于物品的协同过滤模型的混合推荐算法.文章使用真实的大数据评测所提推荐算法,结果显示所提推荐方法能够得到推荐多样性更好且准确率高的结果.     

一种面向HDFS的多层索引技术

SOH（SQL over HDFS）系统通常将数据存储于分布式文件系统HDFS中,采用Map/Reduce或分布式查询引擎来处理查询任务。得益于HDFS以及Map/Reduce的容错能力和可扩展性,SOH系统可以很好地应对数据规模的飞速增长,完成分析型查询处理。然而,在处理选择型查询或交互式查询时,这类系统暴露出性能上的缺陷。本文提出一个通用的索引技术,可以应用于SOH系统中,以提高其查询处理的效率。分析了SOH系统访问HDFS文件的过程,指出了其中影响数据加载时间的关键因素;提出了split层和split内部双层索引机制;设计并实现了聚集索引和非聚集索引。最后,在标准数据集上进行了大量实验,并与现有基于HDFS的索引技术进行了比较。实验结果表明,所提出的索引技术可以有效地提高查询处理的效率。     

符号社会网络中正负关系预测算法研究综述

一些网络中的边根据其潜在涵义可分为正关系和负关系,若用正号和负号来标记网络中的边,则形成一个符号网络.符号网络的应用场景非常丰富,在社会学、信息学、生物学等多个领域广泛存在,逐渐成为当前研究的热点之一.对符号社会网络中链接的正负预测问题进行研究,其成果对社会网络的个性化推荐、网络中异常节点的识别、用户聚类等都具有非常重要的应用价值.主要介绍符号社会网络中正负关系预测问题在国内外的研究现状和最新进展.首先介绍了社会结构平衡理论和地位理论,并将目前主要的预测算法按照设计思路分成两类:基于矩阵的符号预测算法和基于分类的符号预测算法,详细介绍各类算法的基本思路,并从算法效率、准确性和可伸缩性等角度进行详细的对比和分析,总结了符号社会网络预测问题具有的一些特点以及所面临的挑战,同时指出未来可能的发展方向,为相关研究人员提供有价值的参考.     

基于证据链的电子证据可信性分析

随着信息技术的普及与应用,计算机已经成为了人类生活的必需品,同样也成为了犯罪活动中必不可少的工具。计算机留下的电子证据通常会成为案件侦破或审判的核心证据。但是,由于电子证据的易失性和易篡改性,导致其经常在法庭上遭到质疑,因此证明电子证据的可信性是当前取证领域面临的一大挑战。提出的基于证据链的电子证据可信性分析模型通过构建证据链获取关联电子证据 ,并通过判断证据间一致性的方法,进行推理获得电子证据的可信性。     

关系数据库缓冲区置换策略的性能评测(英文)

缓冲区是计算机领域一个非常重要的研究主题。现在存在很多缓冲区置换策略,广泛地用于操作系统、文件系统、数据库以及存储系统中。提出了一种性能评测方法来评测关系数据库的缓冲区置换策略。这种方法采用直接测试方式,使用五个性能指标,包括新提出的指标以及由于模拟方法的局限性在以前的研究中很少使用的性能指标,同时利用显著性测试并提出一种联合使用多个显著性测试的方法进行置换策略之间的比较,设计和使用多种工作负载在单用户和多用户情况下有效地评测各种策略。使用这种评测方法,在一个真实的关系数据库环境中,对十三种典型的缓冲区置换策略的性能进行了详细、全面的实验研究,从中可以获得一些有用的结论。     

多核架构下的数据处理算法优化策略综述

多核处理器,尤其是单芯片多处理器(chip multi-processor,CMP)能够提供强大的共享内存的并行资源,然而单核处理器上的程序和算法并不能充分利用多核架构提供的并行计算资源,因此必须针对多核体系架构特点,对算法进行改进优化,提高算法的执行性能。以优化程序局部性、减少cache访问冲突、提高线程并行度、充分利用单指令多数据流(single instruction multipledata,SIMD)并行和带宽优化等几方面为出发点,归纳和分析了多核处理器上数据处理算法的相关优化策略,并对多核算法进行了总结评述。最后阐述了该领域亟待解决的诸多问题,展望了未来的研究发展方向。     

传感器网络中多近似连续范围查询的处理技术

无线传感器网络为数据库研究开辟了新的研究领域,高效利用节点的有限能量是当前研究的主要目标.如果发布到网络中多个近似连续范围查询不经优化处理而独立执行,会造成节点为不同查询重复发送相同感知数据,从而降低网络寿命.针对近似连续范围查询研究了多查询优化技术,设计了一种索引多维范围查询的多叉树结构rq-kd-tree,通过获取多查询的公共查询部分(查询相交区域)以及基于查询相似度合并相交区域上的多个查询、重写查询.最后,实验证明了所提的算法可以实现能量有效的多查询处理过程.     

基于图形处理器的并行方体计算

方体(cube)计算是数据仓库和联机分析处理(Online analytical processing,OLAP)领域的核心问题,如何提高方体计算性能获得了学术界和工业界的广泛关注,但目前大部分方体算法都没有考虑最新的处理器架构.近年来,处理器从单一计算核心进化为多个或许多个计算核心,如多核CPU、图形处理器(Graphic Processing Units, GPU)等.为了充分利用现代处理器的多核资源,该文提出了基于GPU的并行方体算法GPU-Cubing,算法采用自底向上、广度优先的划分策略,每次并行完成一个cuboid的计算并输出;在计算cuboid过程中多个分区同步处理,分区内多线程并行.GPU-Cubing算法适合GPU体系结构,并行度高.与BUC算法相比,基于真实数据集的完全方体计算可以获得一个数量级以上的加速比,冰山方体获得至少2倍以上的加速.