摘要：离群点检测是数据管理领域中的热点问题之一,在许多方面都有着广泛应用,如信用卡诈骗、网络入侵检测、环境监测等.目前现有的离群点检测算法大多针对集中式的处理环境.但随着数据规模的不断增长,传统的集中式算法处理效率受限,无法满足用户日益增长的需求.针对上述问题,文中提出了一种新型的分布式离群点检测算法.首先,在数据存储阶段(即预处理),提出了BDSP(Balance Driven Spatial Partitioning)数据划分算法.该算法可以有效地均衡每个计算节点的工作负载,并实现良好的过滤效果.此外,为划分所得到的每个块设计了一种全新的编码方式,可以快速地确定块与块之间的相邻关系,降低网络开销.基于BDSP算法,提出了BOD(BDSP-based Outlier Detection)分布式离群点检测算法.该算法包括2个步骤:在每个计算节点本地,利用R树索引进行批量过滤,快速地计算离群点并得到本地候选集;利用BDSP中提供的块编码确定需要相互通信的节点,使用少量的网络开销得到最终结果.最后,通过大量实验验证了文中所提出的BDSP和BOD算法的有效性.实验结果表明,相对于现有算法,文中算法可以显著地提高计算效率并大幅降低网络开销.

摘要：MapReduce是目前最为流行的用于大数据分析的并行系统之一.许多企业已经搭建了自己的MapReduce集群,为广大用户提供计算服务.用户可以向集群提交具有完成时限要求的MapReduce作业,若作业被按时完成,则企业可以获得一定的收益.针对这种应用场景,该文首次提出了MapReduce集群中的最大收益问题.为有效地解决该问题,首先提出了一种基于序列的任务调度策略(简称为SEQ策略),并证明了在处理具有完成时限约束的作业时SEQ策略存在优势.基于SEQ策略,该文提出了最大收益的调度算法(Scheduling Algorithm for Maximum Benefit,简称AMB算法),该算法可以快速地确定可接收作业,并给出有效的执行方案,以达到最大化收益的目的.另外,针对在实际应用中的某些异常情况(如节点宕机),该文也设计了有效的超时处理策略,进一步增加了算法的实用性.最后,通过大量的实验验证了该文所提出算法的有效性.

摘要：图编辑相似查询问题是指从图集G中查询出所有与查询图q的图编辑距离(Graph Edit Distance,GED)在给定阈值τ内的数据图.由于GED计算是NP-Hard问题,现有的研究多采用过滤-验证框架进行查询,对未能过滤掉的图采用A*-GED算法验证.本文提出了分区过滤-增量验证框架PFIV来处理图相似查询问题,在增强过滤效果的同时,还能加快验证速度.首先,在过滤阶段提出了2种分区策略,用来加快分区速度.(1)映射顶点顺序策略:在分区过程中,基于图的特征信息和结构信息提出分区时顶点的映射顺序,尽快过滤掉不相似的图,减少计算量;(2)分区结束条件策略:在分区过程中,设置分区结束条件,加快不相似图的过滤速度.其次,在验证阶段提出了增量验证策略,利用过滤阶段保留的映射结果,设计状态空间树,进行增量验证,加快验证阶段的计算.最后,通过大量实验验证了PFIV能够高效地处理图编辑相似查询问题,对比原有算法,查询效率提高8%~17%,并证明了所提出策略的有效性.