摘要:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

摘要:随着互联网的普及和不断发展，用户通过多个社交网络进行社交活动，使用社交网络带来的丰富内容和服务.通过识别出不同社交网络上的同一用户，可以有助于进行用户推荐、行为分析、影响力最大化.已有方法主要基于用户的结构特征和属性特征来识别匹配用户，大多仅考虑局部结构，且受已知匹配用户数量的限制，提出一种基于全视角特征结合众包的跨社交网络用户识别方法（overall and crowdsourced user identification algorithm，简称OCSA）.首先，利用众包提高已知匹配用户的数量；然后，应用全视角特征评价用户的相似度，以提升用户匹配的准确性；最后，利用两阶段的迭代式匹配方法完成用户识别工作.实验结果表明：该算法可显著提高用户识别的召回率和准确率，并解决了已知匹配用户数量不足时的识别问题.

摘要:随着配备高保真传感器的移动设备的普及以及无线网络资费的快速下降，空间众包作为一种问题解决框架被用于解决将位置相关的任务（如路况报告、食品配送）分配给工人（配备智能设备并愿意完成任务的人）的问题.研究空间众包中最优任务分配问题，关键在于设计出将每个任务分配给最合适的工人的任务分配策略，以使得完成的总任务数目最大化，而所有的工人可以在完成所分配的任务后，在预期最晚工作时间之前返回起点.找到全局最优分配是一个棘手的问题，因为该问题不等于单个工人的最佳分配的简单累加.注意到，仅有部分工人存在任务依赖，因此利用树分解技术将工人分割成独立的集合，并提出一种带启发式的深度优先搜索算法，该算法可以快速地更新启发函数界限，从而高效地对不可能成为最优解的分配方案尽早地进行剪枝.实验结果表明：所提出的方法是非常有效的，可以很好地解决最优任务分配问题.

摘要:社交关系的数据挖掘一直是大图数据研究领域中的热门问题.图聚类算法如SCAN （structural clustering algorithm for network）虽然可以迅速地从海量图数据中获得关系紧密的社区结构，但这类社区往往只表示了社交对象的聚集，无法反馈对象间的真实社交关系，如家庭成员、同事、同学等.要获取对象间真实的社交关系，需要更多维度地挖掘现实中社交对象间复杂的交互关系.对象间的交互维度很多，例如通话、见面、微信、电子邮件等，而传统SCAN等聚类算法仅能够挖掘单维度的交互数据.在研究社交对象间的多维社交关系图数据与传统图结构聚类算法的基础上，提出了一种有效的子空间聚类算法SCA （subspace cluster algorithm），对多维度下子空间的图结构聚类进行研究，目的是探索如何通过图数据挖掘发现对象间真实的社交关系.SCA算法遵循自底向上的原则，能够发现社交图数据中所有子空间的聚类集.为提升SCA的运行速度，利用其子空间聚类的单调性进行了性能优化，进而提出了剪枝算法SCA+.最后进行了大规模的性能测试实验以及真实数据的案例研究，其结果验证了算法的效率和效用.

摘要:随着互联网技术的迅猛发展，社会网络呈现出爆炸增长的趋势，传统的静态网络分析方法越来越难以达到令人满意的效果.于是，对网络进行动态分析就成为社会网数据管理领域的一个研究热点.节点介数中心度衡量的是一个节点对图中其他点对最短路径的控制能力，有利于挖掘社会网络中的重要节点.在图结构频繁变化的场合，若每次变化后都重新计算整个图中所有节点的介数中心度，效率将会降低.针对动态网络中节点介数中心度计算困难的问题，提出一种基于社区的节点介数中心度更新算法.通过维护社区与社区、社区与节点的最短距离集合，快速过滤掉那些在网络动态更新中不受影响的点对，从而提高节点介数中心度的更新效率.真实数据集和合成数据集上的实验结果表明了所提算法的有效性.

摘要:并行环境下的分布式连接处理要求制定划分策略以减少状态迁移和通信开销.相对于数据库管理系统而言，分布式数据流管理系统中的在线θ连接操作需要更高的计算成本和内存资源.基于完全二部图的连接模型可支持分布式数据流的连接操作.因为连接操作的每个关系仅存放于二部图模型的一侧处理单元，无需复制数据，且处理单元相互独立，因此该模型具有内存高效、易伸缩和可扩展等特性.然而，由于数据流速的不稳定性和属性值分布的不均衡性，导致倾斜数据流的连接操作易出现集群负载不均衡的现象.针对倾斜数据流的连接操作，模型无法动态分配查询节点，并需要人工干预数据分组的参数设置.尤其是应对全部历史数据的连接查询，模型效率更低.基于上述问题，提出了管理倾斜数据流连接的框架，使用基于键值和元组混合的划分样式，有效应对二部图模型的各侧倾斜数据.设计了重新动态分配查询节点的策略和状态迁移算法，以支持全历史数据的连接查询和自适应的资源管理.针对合成数据和真实数据的实验结果表明，该方案可有效应对倾斜数据的连接操作，并进一步提升分布式数据流管理系统的吞吐率，特别是降低云环境中的计算成本.

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