大数据计算理论、关键技术与系统

作者: 时间:2017-06-27 点击数:

实验室针对大数据的可计算问题提出了大数据的计算理论,进行了理论创新;针对大数据的可表示问题在大数据的表示与度量方法进行了技术突破;研发了多个系统,在大数据查询处理、社交媒体数据分析、知识图谱与问答系统和非结构化大数据管理方面得到重要应用。

1.大数据计算理论

大数据带来了数据量与计算有效性的矛盾。一方面,规模过大的数据量降低了算法的运行效率;另一方面,规模过小的数据量可能无法得到可接受的计算结果。因此,在大数据计算过程中,必须在数据量和计算有效性间实现均衡,带来最好的计算效率和效果。作为大数据计算的基础,实验室从数据量与计算有效性间的均衡角度重新审视了传统的计算复杂性理论和算法理论,针对大数据的可计算问题提出了大数据计算的易解性理论,识别了大数据真正易解的问题;针对大数据非易解类问题,提出了大数据查询处理的有界可评估性理论和并发可扩展性理论,克服了非易解类问题的难解性;针对大数据的可近似性,提出了大数据近似理论,把近似思想应用于大数据挖掘与搜索,提出了多模式哈希近似查询方法。

(1) 大数据计算的易解性理论。传统计算复杂性理论认为,可根据问题是否存在多项式算法,将一个问题定义为易解问题或难解问题。然而,在大数据计算中,多项式时间复杂度甚至线性时间复杂度的算法在实际应用中已变得不可接受。因此,针对传统计算复杂性理论对易解性问题的定义不适用于大数据计算的问题,实验室提出了大数据计算的易解性复杂性理论,定义了大数据计算背景下的可行算法的复杂性边界;识别了研究大数据计算中与可行算法对应的的易解问题类;建立了大数据驱动的易解类完全理论,被大数据领域顶级会议VLDB的审稿人评价为将开辟学术界和产业界新的方向”

(2) 大数据查询处理的有界可评估性理论。大数据下的查询处理面临的一个关键问题是如何识别只需处理的“小数据”而无需处理大数据。实验室建立了查询处理的有界可评估性模型与理论分析,对针对关系数据查询处理中小数据的存在性问题和可识别性问题进行了建模和理论分析,对关系查询的有界可评估性建立了等价的语法,并对大数据有界可评估的查询设计了查询规划生成算法。

(3) 大数据查询处理的并发可扩展性理论。图数据是一类大数据,在社交网络、知识图谱等领域应用广泛。针对分布式大数据计算的有效性问题,研究了大数据计算的并发可扩展性问题,即在分布式环境下,随着计算节点的增多,确实可以增加效率,不会引起通信开销的巨增。建立了大数据图数据查询处理的并发可扩展性理论,得到了图数据查询处理具有并发可扩展性的充分必要条件,识别出具有并发可扩展性以及不具有并发可扩展性的常用图查询,对基于图模式的图数据查询提出了并发可扩展算法的设计方法。

(4) 大数据近似理论与方法。传统近似算法能在短时间内获得有效的近似解而得到广泛应用。然而面向大数据,传统的近似算法同样遇到如何只访问一部分数据就能取得有效近似解的问题。实验室提出了资源有限下的大数据近似计算研究的数据驱动近似理论。同时,针对图像、视频等非结构化数据内容复杂、多样的问题,在国际上较早较系统地研究了非结构化大数据多模式哈希近似查询方法,提出了特征分布感知、多种特征融合、底层特征和语义特征融合以及哈希选择等哈希搜索方法。针对非结构化大数据多哈希表快速索引和高效计算进行了深入的探索,在国际上率先提出并研究了互补哈希索引机制,探索了哈希索引在大规模机器学习和数据挖掘中的哈希加速应用,多项成果达到国际领先水平。

2.大数据的表示与度量方法

多源性与异构性是大数据的重要特征,对大数据进行有效和高效的表示与度量是大数据计算的前提条件。为此,实验室在大数据的表示方法与度量机制方面进行了关键技术的突破。

 (1) 基于深度学习建立非结构化数据语义标注和相似度量。首先研究了基于隐藏层白化的深度神经网络训练性能提升方法,提出深度网络隐藏层的输出进行白化操作,改善了神经网络参数空间条件数,获得更高的学习率(高达20或30倍)且不易发散;其次,研究了基于半监督学习的大规模数据标注技术,提出了一种在线半监督标注框架和基于代理的全局一致性传播方法,提高了标注的准确性和效率;同时基于深度学习和本体还研究了非结构化数据语义相似性计算方法,利用语义轮廓承载了研究目标、方法和领域等关键信息,利用深度学习得到语义轮廓元素的词向量表达,实现了基于本体和领域语料联合进行词汇嵌入表达的模型。

(2) 面向关系的知识表示学习方法。为解决大规模数据的异构与多样性问题,针对知识管理与计算智能中的实体、关系及知识体系,提出了面向关系的表示学习方法,统一大规模海量数据的统一表示。一方面,对于面向大数据的突发事件分析与预警,利用多源异构数据的量化表示方法,探索微博数据量化表示与管理技术,基于近似算法理论和多粒度存储机制,研究突发事件的预警、跟踪和回溯等技术,解决微博数据的探索式数据挖掘问题,研制突发事件分析和预警系统。

3.大数据查询与分析系统与应用

实验室研发了多个系统,在大数据通用计算引擎、社交媒体数据分析、知识图谱与问答系统和非结构化大数据管理方面得到重要应用。

(1) 大数据查询处理引擎。基于查询可评估性算法与顺序图算法的自动并行化这两个算法研究成果,分别针对关系数据和图数据开发了两个大数据通用计算引擎:BEAS与GRAPE。其中,BEAS系统核心方法目前已应用于华为技术有限公司MPPDB以及大数据平台查询优化器的技术原型并实现了初步应用,在原有系统基础上效率提高40倍,最高达到5个数量级,具有良好的商业应用前景;GRAPE系统与华为共同用社交网络com-friendster数据集与2012年全互联网的网页连接图clueweb12做测试,验证了重要的图数据计算场景,如: k-hop问题等,可以在秒级时间内计算完成,并减少了冗余计算。

(2) 社交媒体数据分析系统Ring。通过研究近似算法理论和多粒度存储机制,系统存储索引层采用开源工具HBase与ElasticSearch实现,以支撑微博数据存储,全文关键词索引与查询,数据统计等功能。经过优化可以支撑2亿/天的数据吞吐量;设计了事件关联和层次分析算法,实现微博事件的实时检测。检索系统的分布式计算框架采用Yarn Spark的内存计算架构,并实现基于Spark分布式内存计算的微博分类,微博数据统计,事件地理位置分析,实时热点关键词监测,实时异常事件检测等模型。该系统在北京航空航天大学的32节点PC集群中,使用10台机器搭建分布式微博爬虫系统,该爬虫每日可爬取1000万条微博数据,可以得到用户信息,并可构建微博转发路径。在安全中心部署突发事件监测系统,包含前期开发全部功能,可以支撑每天亿级数据的存储、索引和事件分析。实现了安全中心实时全量微博数据的接入,用户数据库查询接入,并对安全中心检索系统进行了初步测试。此外,还提出了一种新的面向微博短文本数据实时事件检测算法,仅使用4台服务器即可处理全量微博数据;该方法可以进行早期异常事件预警,评估事件异常等级并预测其热度,能够自动追踪事件的发展,该方法已经实现系统集成。

(3) 知识图谱。在互联网信息智能理解方面:根据对Web页面数据、日志数据及用户行为数据的处理分析,构建知识网络及用户兴趣模型,提升互联网信息的语义理解能力并为搜索用户并提供个性化的内容推荐,提升用户搜索体验,培育新兴数据服务产业。基于互联网数据,创建基于语义的链接关系,从海量的数据中提取出精华信息,完成了知识的汇集、整理、加工,目前已建成涵盖近20个领域、超千万实体量的庞大知识数据库,为用户带来多角度、全方位的搜索体验提升。同时研究海量的互联网数据和深度语义理解的深度问答系统技术,研发了实体知识体系建模技术和文本分析和关系抽取技术。并实现了流式计算平台,并将上述技术应用于文本分析、智能推荐和大数据预测等应用场景中。

(4) 非结构化数据管理系统。基于大数据查询理论和四面体数据模型,研发了非结构化数据管理系统,设计和实现了图像和视频等非结构化大数据的分布式检索系统,已经成功应用于国家某中心互联网图像数据管理,支持十亿级规模的图像秒级精确检索。同时在交通、航空、医学和科技等领域进行了规模化应用。相关研究还在京东等企业上线使用,大幅提高了产品图像大数据的搜索精度。研发了基于哈希的大规模网络视频去重系统,实现了基于时序的排序验证方法,在央视华夏微电影、公安部第三研究所等相关平台中部署使用,在网络安全、版权保护等方面发挥了重要作用。

在大数据的计算复杂性与算法理论等研究成果发表在ACM Transaction on Database Systems、IEEE Transaction on Knowledge and Data Engineering、Theoretical Computer Sciences、IEEE Transactions on Image Processing等数据库、模式识别与计算机理论等领域的顶级期刊,以及SIGMOD、VLDB、ICDE、PODS、CVPR、AAAI等顶级国际会议上。并获得SIGMOD 2017最佳论文奖、PODS 2015 时间检验奖、2014 ICDE最佳论文提名奖。

软件开发环境国家重点实验室 地址:北京市海淀区学院路37号北京航空航天大学新主楼G座
邮编:100191 联系电话:010-82338092 邮箱:nlsde@nlsde.buaa.edu.cn