软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2018年第03期杂志 文档列表

软件学报杂志基于图结构的大数据分析与管理技术专刊

基于图结构的大数据分析与管理技术专刊前言525-527

摘要：作为一种常用的描述事物之间复杂关联关系的普适结构，图结构被广泛用于表示万维网、社交网络、蛋白质交互网络、化学分子结构、软件代码剽窃检测、复杂对象识别、公路网络、模式识别、超大规模集成电路设计和生态系统中的食物链等．图结构在大数据价值发现中也发挥着重要的作用，如何对基于图结构的大数据进行有效的分析和管理，已成为学术界和工业界关注的新的热点．研究人员提出了很多新颖的图算法，如图生成器、图的可达性判定、相似子图查询、图的特性分析、图查询语言、图上的关键字查询、社交网络分析等，也出现了一些开源的图数据库系统．但总体而言，针对基于图结构的大数据的研究仍然处于起步阶段，还有很多需要研究的问题．

流式处理的异步图处理框架528-544

摘要：分布式图计算是目前处理大图数据的主流技术，但是存在诸多无法避免的问题，比如分布式计算的负载均衡和分布式实现的调试和优化仍然非常困难．另一方面，近几年的研究结果表明：通过设计合理的数据结构和处理模型，在单个PC上基于大容量磁盘的大图计算往往可以获得与分布式图计算相当的处理性能．例如，GraphChi在单机上的处理性能与Spark在50台节点上的处理性能相差无几．结合累加迭代计算和单机并行处理技术，提出流式处理的异步计算模型ASR它实现了对磁盘的完全顺序访问，允许流式的顺序载入结构数据的同时进行异步更新计算．基于ASP模型，提出了一种流式处理的异步图处理框架S-Maiter,实现了高效率的基于外存的单机大图处理，通过I／O线程优化、内存资源监控、shard级优先级调度等优化技术，提高了系统处理大图数据的性能．实验结果表明：在处理大图数据（1300万顶点，5亿连边）时，仅仅需要1台PC机计算资源的S-Maiter与在16台PC上运行的分布式Maiter的性能几乎相当．并且，S．Maiter比另外一个流行的单机大图处理系统GraphChi要快1．5倍．

路径-维度GraphOLAP大规模多维网络并行分析框架545-568

摘要：现实生活中，大量数据都可以使用多维网络进行建模．如何更好地对多维网络进行分析，是研究人员关注的重点．OLAP（联机分析处理）技术已被证实是对多维关系数据进行分析的有效工具，但应用OLAP技术管理与分析多维网络数据以支持有效决策，仍是一项巨大的挑战．设计并提出了一种图立方体模型：路径．维度立方体，并针对提出的立方体模型将物化过程划分为关系路径物化与关联维度物化两部分，分别提出了物化策略，并基于Spark框架设计了相关算法．在此基础上，针对网络数据设计并细化了相关的Graph OLAP（联机分析处理）操作，丰富了框架的分析角度，提高了对多维网络的分析能力．最后，在Spark上实现了相关算法，通过对多个真实应用场景中的数据构建多维网络，在分析框架上进行了分析，实验结果表明，所提出的图立方体模型和物化算法具有一定的有效性和可扩展性．

分布式图处理系统技术综述569-586

摘要：图作为一种基本的数据类型，是对现实世界中对象及其关联关系的一种抽象．现实中，许多科学问题都可以被模型化为图的问题，因此，对图数据进行分析非常重要．图数据分析在语义Web分析、社交网络、生物基因分析以及信息检索等领域有着广泛的应用．随着移动互联、物联网等信息技术的发展，图数据的规模处于持续增长的状态．为了能够应对大规模图数据的高效分析和计算，Google提出了Pregel分布式图处理框架．此后，学术界和工业界提出了许多基于Pregel框架的优化技术和系统实现．在充分调研和分析的基础上，首先总结出分布式图处理系统的3个优化目标：其次，从计算粒度、任务调度、通信方式、负载划分这4个维度，综述现有分布式图处理系统中的各类优化技术；最后对该领域未来的研究内容和发展方向进行了探讨与展望．

Coteries轨迹模式挖掘及个性化旅游路线推荐587-598

摘要：Coterie是一种异步的组模式，要求在不等时间间隔约束下，找出具有相似轨迹行为的组模式.而传统的轨迹组模式挖掘算法往往处理具有固定时间间隔采样约束的GPS数据，因此无法直接用于Coterie模式挖掘.同时，传统组模式挖掘存在语义信息缺失问题，降低了个性化旅游路线推荐的完整度和准确度.为此，提出基于语义的距离敏感推荐策略DRSS （distance-aware recommendation strategy based on semantics）和基于语义的从众性推荐策略CRSS （conformity-aware recommendation strategy based on semantics）.此外，随着社交网数据规模的不断增大，传统组模式聚类算法的效率受到极大的挑战，因此，为了高效处理大规模社交网轨迹数据，使用带有优化聚类的MapReduce编程模型来挖掘Coterie组模式.实验结果表明：MapReduce编程模型下带优化聚类和语义信息的Coterie组模式挖掘，在个性化旅游路线推荐上优于传统组模式旅游路线推荐质量，且能够有效处理大规模社交网轨迹数据.

基于距离度量的多样性图排序方法599-613

摘要：有效结合查询相关性和多样性的扩展相关性，是多样性图排序问题的一种优化目标．基于扩展相关性的多样性图排序可建模为一个子模函数优化问题，贪心子模优化算法可近似求解该问题．然而，扩展相关性不能直接度量节点间的不相似性．子模优化算法是串行算法，不能充分利用诸如Spark等集群计算平台有效提高算法效率．针对这些问题．提出一种描述节点间不相似性的距离度量．基于该距离度量，将多样性图排序问题建模为一个在查询相关节点集上构造的带权完全图的最大和k-dispersion优化问题．提出了求解该问题的多项式时间2-近似算法．鉴于不同节点对的距离度量计算是相互独立的，进一步提出了基于MapReduee编程模型的并行化多样性图排序算法．最后，在真实图数据集上验证了所提出算法的高效性和有效性．

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

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

基于MapReduce的图结构聚类算法627-641

摘要：图结构聚类（SCAN）是一种著名的基于密度的图聚类算法，该算法不仅能够找到图中的聚类结构，而且还能发现图中的Hub节点和离群节点．然而，随着图数据规模越来越大，传统的SCAN算法的复杂度为O（m1.5）（m为图中边的条数），因此很难处理大规模的图数据．为了解决SCAN算法的可扩展性问题，提出一种基于MapReduce的海量图结构聚类算法MRSCAN，这是一种计算核心节点以及两种合并聚类的MapReduce算法．最后，在多个真实的大规模图数据集上进行实验测试，实验结果验证了算法的准确性、有效性以及可扩展性．

路网环境下的最近邻查询技术642-662

摘要：最近邻查询作为基于位置服务的重要支持性技术之一，引起了众多学者的广泛关注和深入研究．相对于欧式空间而言，路网环境下的最近邻查询更贴近人们的生活，有着更重要的研究意义．路网环境下庞大的数据量和复杂的数据结构，使得最近邻查询的操作代价变得非常昂贵，如何有效地提高查询效率，是研究者面临的主要挑战．对路网环境下的最近邻查询技术进行综述，分别从最近邻查询采用的索引结构和查询处理过程对现有路网环境下的最近邻查询方法进行了分析和比较，也介绍了路网环境下最近邻的变体查询技术的研究情况，最后探讨路网上最近邻查询技术未来的研究重点．

动态图模式匹配技术综述663-688

摘要：随着大数据时代的到来，多源异构数据的快速增长已经成为开放性问题，数据之间的内在关联通常可以用图数据的形式来表现．然而在实际应用中，例如网络安全分析和社交网络舆情分析，描述实体对象之间关系的图数据的结构和内容往往不是固定不变的，图数据的结构以及节点和边的属性会随着时间的推移发生更新变化。因此，如何在动态更新的图数据中进行高效的查询、匹配，是目前研究的热点问题．从关键技术、代表性算法和性能评价方面概述动态图模式匹配技术的研究进展．最后，对动态图模式匹配技术的典型应用、面临的挑战问题和未来发展趋势进行了总结和展望．

基于SQL的图相似性查询方法689-702

摘要：图作为一种表示复杂信息的数据结构，被广泛应用于社交网络、知识图谱、语义网、生物信息学和化学信息学等领域．随着各领域应用的普及和深入开展，如何管理这些复杂图数据，是目前图数据库技术面临的巨大挑战．图的相似性查询是图数据管理中的热点问题之一，对图查询问题的研究主要包括图的相似性查询等．重点研究基于编辑距离（graph edit distance）的图相似性查询处理问题．首先，通过对目前代表性的问题求解算法分析发现，目前已提出的过滤规则都具有自己的优缺点和适用性．其次，针对已有方法在过滤阶段自身存在的优缺点和适用性的问题，提出一种面向关系型数据库的过滤框架新的过滤框架可以支持所有已有的过滤规则，从而通过结合不同的过滤规则来优化图相似查询算法以提高查询效率．该方法可以最大程度地保留不同过滤规则的优点并克服其缺点，从而对不同查询具有普遍适用性．最后，基于PubChem教据集，通过比较算法在求解查询结果的时间消耗，验证所提出算法的高效性及可扩展性．实验结果表明，所提出的方法优于现有算法．

路网环境下兴趣点查询的隐私保护方法703-720

摘要：近年来，无线通信技术的迅猛发展推动了基于位置服务（location-based services，简称LBS）的发展进程而其中，兴趣点（pointofinterest，简称POi）查询是基于位置服务最重要的应用之一．针对在路网环境下，用户查询过程中位置隐私泄露的问题，提出了位置k匿名隐私保护方法．首先，匿名服务器将兴趣点作为种子节点生成网络Voronoi图，将整个路网划分为相互独立且不重叠的网络Voronoi单元（network Voronoicell，简称Nvc）．其次，利用Hilbert曲线遍历路网空间，并按照Hilbert顺序，对路网上所有的兴趣点进行排序．当用户发起查询时，提出的匿名算法通过查找与用户所在NVC的查询频率相同且位置分散的扣1个NVC，并根据用户的相对位置在NVC内生成匿名位置，从而保证了生成的匿名集中位置之间的相互性，克服了传统如匿名不能抵御推断攻击的缺陷．理论分析和实验结果表明，所提出的隐私保护方案能够有效地保护用户位置隐私．

基于疾病信息网络的表型相似基因搜索721-733

摘要：人类基因组计划的成果推动了生物信息学研究的发展．基于疾病表型相似性策略寻找功能上存在联系的致病基因，即表型相似基因，具有重要的研究价值和广阔的应用前景，是新兴的研究热点．然而，生物医学领域尚没有利用计算机方法开展基于基因．疾病．表型关系网络的表型相似基因搜索研究对此，利用疾病公开数据库构建了包含基因、疾病、表型这3类异构类型节点的疾病信息网络，并设计了基于疾病信息网络的相似基因搜索算法gSim-Miner．针对疾病表型数据的特点，设计了剪枝策略提高算法效率．通过在真实数据上的实验，验证了疾病信息网络对搜索表型相似基因的适用性以及gSim-Miner算法的有效性、执行效率和可扩展性．

路网感知的在线轨迹压缩方法734-755

摘要：随着定位技术的高速发展，定位传感器被广泛应用于智能手机、车载导航等移动设备中，用于采集移动对象位置数据并将数据上传至服务器．该技术的应用方便了位置跟踪、预测和分析，同时也带来了轨迹数据量大、数据冗余、传输和存储代价高等问题．轨迹压缩技术即是针对该问题而提出的，它通过保留关键轨迹点和去除冗余轨迹点信息，降低了轨迹数据的传输和存储开销．分析了近年来轨迹压缩领域的研究进展，针对现有研究工作的不足，提出了一种路网感知的在线轨迹压缩方法，包括针对轨迹压缩的距离有界的隐马尔可夫地图匹配算法和误差有界的高效轨迹压缩算法等，实现了该方法的原型系统ROADER（road-network aware and error-bounded trajectory compression）．基于真实数据集的实验结果表明，该系统在压缩率、误差和执行时间等方面均显著优于同类算法．

基于边采样的网络表示学习模型756-771

摘要：近年来，以微博、微信、Facebook为代表的社交网络不断发展网络表示学习引起了学术界和工业界的广泛关注．传统的网络表示学习模型利用图矩阵表示的谱特性，由于其效率低下、效果不佳，难以应用到真实网络中．近几年，基于神经网络的表示学习方法因算法效率高、较好地保存了网络结构信息，逐渐成为网络表示学习的主流算法．网络中的节点因为不同类型的关系而相互连接，这些关系里隐藏了非常丰富的信息（如兴趣、家人），但所有现存方法都没有区分节点之间边的关系类型．提出一种能够编码这种关系信息的无监督网络表示学习模型NEES（network embedding via edge sampling）．首先，通过边采样得到能够反映边关系类型信息的边向量；其次，利用边向量为图中每个节点学习到一个低维表示．分别在几个真实网络数据上进行了多标签分类、边预测等任务，实验结果表明：在绝大多数情况下，该方法都表现最优．

社交网络高效高精度去匿名化算法772-785

摘要：自从社交网络成为重要的研究课题，社交网络隐私保护也成为了重要的研究内容，尤其是关于公开以供研究的大规模社交网络图数据的隐私保护．为了评估用户的隐私风险，研究者们设计了不同的方法对图进行去匿名化，在不同的图网络中识别个体的身份．但是，当前的去匿名化算法或者需要高质量的种子匹配，或者在精确度和效率上颇有不足．提出一种高效高精度的无种子去匿名化算法RoleMatch，基于社交网络的拓扑结构识别个体身份．该算法包括：（1）可以快速计算的两图结点间相似度度量方法RoleSim＋＋；（2）一种有效的结点匹配算法，此法同时考虑了结点间的相似度和中间匹配结果的反馈．在实验部分，利用Live Journal的数据，用RoleMatch对比了多种流行的匿名化算法，并根据实际应用情景，在传统实验的基础上增加了局部去匿名化的实验，实验结果验证了所提出的去匿名化算法的优秀性能．

一种融合节点先验信息的图表示学习方法786-798

摘要：图表示学习是实现各类图挖掘任务的基础．现实中的图数据不仅包含复杂的网络结构。还包括多样化的节点信息．如何将网络结构和节点信息更加有效地融入图的表示学习中，是一个重要的问题．为了解决这一问题，基于深度学习，提出了融合节点先验信息的图表示学习方法．该方法将节点特征作为先验知识，要求学习到的表示向量同时保持图数据中的网络结构相似性和节点特征相似性．该方法的时间复杂度为D（｜V｜），其中，｜V｜为图节点数量，表明该方法适用于大规模图数据分析．同时，在多个数据集上的实验结果表明：所提出的方法相比目前流行的几种基线方法，在分类任务上能够获得良好而稳定的优势．

基于循环神经网络的数据库查询开销预测799-810

摘要：在数据库负载管理、性能调优过程中，开销预测模型是提高其效率的关键技术．首先，由于数据库系统的复杂性和计算机资源的竞争，很难精确地估计不同操作的开销；其次，现有的研究大多没有真正预测查询的执行时间，而是预测了类似查询优化器中开销模型生成的开销：由于查询计划结构的复杂性，现有研究更多地使用了笼统的查询信息，而很少利用查询计划中操作层面的信息，并依据这些信息来获得开销模型．为了减少负载管理的复杂性，提出了基于循环神经网络的精细模型来预测查询开销，以查询计划中的操作行为及其实际运行时间作为特征提取的来源．特别地，考虑到查询计划结构的复杂性。采用一种特殊的循环神经网络——长短期记忆（long-short term memory,NLSTM）．给一个特定的查询计划，在该计划实际执行之前，模型就能产生其预测的执行时间区间．这会比现有数据库的查询优化器产生的开销预估结果（任意单位）更具有参考性，也优于需要在执行开始之后才能预测的查询进度指示器．所提方法预测查询执行时间，可以解决数据库负载管理中的关键问题．通过实验验证，模型的正确率高于71％，在一定程度上证明了方法的可行性．