数据密集型科学与工程：需求和挑战

科学研究在经历了实验科学、理论科学、计算科学阶段后,进入了数据密集型科学阶段,与之相伴的是大数据时代的到来.大数据泛指规模达到几百TB,甚至PB级的数据①,其典型的特征是分布、异构、低质量等.尽管传统数据库管理技术(特别是商业关系型数据库)在过去40年间取得了巨大成功,但是这些技术和系统无法有效管理支持数据密集型科学与工程(Data-Intensive Science and Engineering,DISE)的大数据.文中探讨数据密集型科学与工程的具体需求和现实挑战.它涵盖的内容表现在4个层面,包括数据存储与组织、计算方法、数据分析以及用户接口技术等.同时,数据质量、数据安全、数据监护等内容也需要在各层面得到重视.文中尝试梳理了数据密集型科学与工程的整体架构,回顾了相关领域的新近发展,分析了面临的挑战,探讨了未来的研究方向.

数据流处理技术在电信网管系统中的应用

网络流量监测技术是电信运营商所关注的重点之一。随着网络传输带宽的不断增加,传统的基于磁盘的处理技术已经不能够满足运营管理的需要,数据流处理技术的出现为网络流量监测应用提供了一种新的解决方案。SMART[1,2]和RealMon[3]是将数据流处理技术应用于网络流量监测的两个应用系统。文中结合上海电信在骨干网流量监测上的应用需求,对这两个系统的设计与应用进行了介绍。SMART系统以数据流上的频繁项挖掘算法为基础,支持NetFlow数据流上长时间滑动窗口内的Top-K查询,实现了对网络流量分布的实时监测。RealMon系统采用数据流上的降维分析算法对SNMP数据流进行分析,通过监测网络链路上不同流量数据的相关性变化来发现异常流量。实验和在真实环境中的应用表明,SMART和RealMon系统能够满足骨干网流量监测应用的需要,并且极大地提高了监测系统的性能。

基于用户分组的广告定位(英文)

在线广告在当今的电子商务时代中扮演者愈加重要的角色.在线广告依靠其灵活的内容推荐和个性化推荐,与报纸、电视等传统媒体相比具有更高的精确性.广告定位的应用可以精确地将广告推送给对其感兴趣的用户.本文讨论研究领域和工业领域中所使用的广告定位技术,并阐述基于用户分组来进行广告推送可以大幅度的提高广告的点击率(CTR).

Web数据管理研究现状与发展方向

万维网(World Wide Web)在世界范围内的飞速发展,使得Web逐渐成为一个主要的计算平台和各类信息发布的重要方式.目前许多研究机构对在国际互联网(Internet)和企业内部互联网(Intranet)环境下的信息搜集、共享和传递产生了兴趣,并展开了广泛的研究.

高维空间中的离群点发现

在许多KDD(knowledge discovery in databases)应用中,如电子商务中的欺诈行为监测,例外情况或离群点的发现比常规知识的发现更有意义.现有的离群点发现大多是针对数值属性的,而且这些方法只能发现离群点不能对其含义进行解释.提出了一种基于超图模型的离群点(outlier)定义,这一定义既体现了“局部”的概念能很好地解释离群点的含义.同时给出了HOT(hypergraph-based outlier test)算法,通过计算每个点的支持度、隶属度和规模偏差来检测离群点.该算法既能够处理数值属性,又能够处理类别属性.分析表明,该算法能有效地发现高维空间数据中的离群点.

计算广告:以数据为核心的Web综合应用

计算广告是随着互联网应用发展起来的一个综合多学科的研究领域,这多学科包括数据管理、信息检索、数据挖掘、统计分析、机器学习、分布式系统等.由于其广泛的应用和巨大的市场价值,计算广告学已逐步发展成一个独立的研究方向.目前,计算广告学涵盖在线广告投放、移动终端广告投放、社会网络应用广告投放、用户信息分析等.文中主要介绍计算广告学的演化过程,包括计算广告投放模式的演化(由按合约投放演变为实时竞价投放)、计价模式的演化(由按展示计价演变为按点击计价、按交易计价等)、投放目标的演化(由品牌效果展示演变为直接市场营销);计算广告学的组成部分,包括计算广告产业链(如广告主、网络媒体、联盟网络、广告交换、需求方平台、销售方平台等)、计算广告的分类(如条幅展示广告、赞助商搜索、联盟广告等).此外,文中还重点讨论了广告检索、排序投放算法以及广告离线分析、实时投放平台等关键技术和平台.最后,还将讨论在移动计算环境下的移动终端的广告投放、基于位置信息的广告投放、基于社会网络的广告投放等新型应用模式对计算广告学发展的影响.

XML文档在关系数据库中的规范化存储

提出了一种存储方法 ,首先把 XML 文档映射为泛关系模式 ,再利用算法 Derive FDs推导出 XML 键所蕴含的泛关系模式上函数依赖集的规范覆盖 ,根据此规范覆盖 ,最后将泛关系模式保持函数依赖地分解为 3NF模式集 .得到了保持 XML 键约束的规范化存储模式 ,实现了 XML 文档在关系数据库中的规范化存储 .

基于高维空间的在线高效子空间Skyline算法——CSky

Skyline计算是要发现数据集中不被其他点支配的所有点的集合.近来,它在实时在线服务方面的良好应用前景,使其成为数据库研究领域的一个热点.实际应用中,用户通常期望快速、渐进地返回Skyline计算结果,因此文中主要讨论了高维空间子空间Skyline渐进查询问题.据我们所知,现有的Skyline计算方法都不能直接或者通过简单修改来高效解决该种查询问题.BNL(Blocked Nested Loop)算法是一个可用来进行子空间Skyline计算的算法,但是,该方法低效且非渐进.基于此,文中提出了在线高效子空间Skyline算法——CSky(Count the Skyline).该算法充分利用了一个新颖数据结构——InvertS的特征,即通过对目标数据集进行排序,存放最可能为Skyline点的数据于算法优先扫描的位置,这使得CSky算法能高效计算出任意子空间上的Skyline;同时,CSky每次计算子空间Skyline查询时,至多访问一遍数据库;再有,算法扫描一个点时,只需和当前已发现的Skyline点进行比较即能判断该点是否为Skyline点,保证了算法的渐进性.这样,相比BNL,CSky大大减少了计算开销,具有其他基于索引的Skyline算法计算Skyline时的高效,且这种高效适用于所有子空间.理论分析和实验表明,在解决高维空间子空间Skyline查询问题方面,CSky性能大大优于BNL.

在线广告投放系统及技术的演变

通过对在线广告市场的背景及相关技术的介绍,从广告的形式和投放位置这两个维度对在线广告进行划分,给出了涵盖在线广告领域现有及潜在广告形态的分类体系,分析了不同形态广告投放技术的差异.通过对在线广告投放平台演变和发展的了解,概述了以广告服务器、广告网络、广告交换平台为主的广告投放系统的架构及技术演变,为计算广告相关研究工作提供了关于在线广告投放系统的背景参考和技术概览.

逆向序敏感查询在互联网广告投放中的应用

产品和用户之间的信息匹配,是互联网广告投放中需要解决的关键问题.本文介绍了在信息匹配过程中所用到的几个关键的数据库查询技术,给出了它们的形式化定义和扩展型SQL表述,并且将重点放在了逆向序敏感查询上.同时,还描述了一个具体的例子来对这几种查询方法进行形象化的展示.最后,对这几种查询进行了总结和展望.

SMART:基于数据流技术的电信网络流量监控系统

大多数国内电信运营商现有的网络流量监控系统的分析都是基于数据文件的操作模式,处理速度远跟不上大量数据到达的速度。基于这种情况,提出了基于数据流技术来实现在线网络流量监控系统SMART。SMART收集多个路由器发送的NetflowV5或者V9格式的数据,并将其转换成用户定义的监控流;以滑动窗口的方式查询输出流量构成中Top-k频繁数据信息;监测网络流量突变;以可视化的图形和报表形式显示结果。SMART先进的数据流算法技术基础和完整的系统框架设计使得它在上海电信高效稳定的7*24h运行。

一种基于曝光量和点击率的用户组优化策略

行为定向技术在网络广告投放过程中起着非常重要的作用,其中最关键的就是对用户进行分组.好的用户分组策略能够产生高质量的用户组,对用户组内的用户投放广告能够有效提高点击量(曝光量×点击率).传统的用户分组策略评估方法重点考虑点击率(click-through rate,CTR)提高程度,忽略了曝光量(impression)的重要性.曝光量受到用户数量的影响,当用户组中的用户数量达不到一定值时,看到广告的用户数量很少,导致曝光量非常少,即使广告的CTR很高,点击量和广告转换量也会非常少,针对这样的用户组投放广告不会为广告主带来特别大的收益.针对曝光量小的用户组,提出一种用户组优化算法,可保证最终分组结果同时具备高的CTR提高程度和曝光量.在真实数据集上进行实验,结果表明经过优化之后的用户组在保证CTR的同时大幅度提高了曝光量和点击量.

集群环境下分布式索引的实现

针对分布式存储系统上使用非主键访问数据带来的性能问题,探讨在分布式存储系统上实现索引的相关关键技术。在充分分析分布式存储特征的基础上,提出了分布式索引设计和实现的关键点,并结合分布式存储系统的特点及相关的索引技术,讨论了索引的组织形式、索引的维护和数据一致性等问题;然后基于如上的分析,选择在分布式数据库系统OceanBase开源版本上,设计和实现分布式索引机制,并通过基准测试工具YCSB进行性能测试。实验结果表明,虽然辅助索引会对系统性能产生影响,但因为充分考虑了系统特征及存储特点,在不同数据规模下,该索引都能够将性能影响控制在5%以内。另外,使用冗余列的方式,能进一步将该索引的性能提升100%。

面向上下位关系预测的词嵌入投影模型

上下位关系是自然语言处理领域中的重要概念,用于描述概念之间的从属关系.上下位关系的精准预测,有助于挖掘概念之间的内在层次结构,是构建大规模语义网络、知识本体、知识图谱等知识密集型系统的重要基石.传统上下位关系的预测算法大多依赖较为固定的语言模式,因而具有低覆盖度、高人工干预等缺陷.此外,语言模式与语言本身的特性高度相关,在中文等表述灵活的语言中预测精度较低.随着深度学习技术在自然语言处理领域迅猛发展,词嵌入技术被广泛应用于建模词之间的语义关系.特别地,词嵌入投影模型学习如何将下位词的词向量投影到上位词的词向量,显式地建模了上下位关系的关系表示.基于已有经典研究以及最新成果,本文详细论述了词嵌入投影模型的发展过程和最新研究进展,包括基于迭代学习、转导学习、对抗学习等深度学习技术在词嵌入投影模型上的改进.在实验中,我们对多个词嵌入投影模型在中文和英文的公开数据集上进行充分详细的评测,探讨了不同的词嵌入投影模型在不同学习场景下的优缺点.最后,在面向特定领域和长尾上下位关系抽取等问题上探讨了未来的研究展望.

多级混洗交换网络开关选择的二分算法

多级混洗交换网络是高性能计算机体系结构中极为重要的一种互连网络连接体系结构,本文提出了一种新的开关选择算法,可以在实际应用中有效提高计算机的性能。

微服务架构下的分布式事务处理

单体架构下的分布式事务是一个服务内访问多个数据源的分布式事务,可以采用传统分布式事务处理模型——DTP(Distributed Transaction Processing)模型来解决。在微服务的架构下,可能会出现跨服务、跨资源的分布式事务。在解决这类分布式事务时,微服务追求系统的可用性和最终一致性而非数据的强一致性。针对不同的微服务分布式事务场景,介绍不同的分布式事务处理模型,包括可靠消息模型、业务补偿模型和TCC(TryConfirm/Cancel)模型,并总结每种模型的处理流程和优缺点。对TCC模型在性能上和可移植性上提出优化方案。

基于Map/Reduce的分布式数据排序算法分析

为了解决大规模数据的存储与计算,近年来分布式系统得到了大量的应用.如何在分布式系统中对大规模数据集进行排序是影响许多应用性能的基础问题,其中不仅涉及每个节点上排序算法的选择,更重要的是设计协调各节点的分布式算法.本文总结了分布式系统中常用的分布式排序算法,对每种算法的执行流程、代价模型和适用场景进行了分析,并通过实验对分析结果进行了验证.本文的工作可以帮助开发人员选择和优化分布式环境下大规模数据排序的算法.

RealMon:处理低质量SNMP数据流的实时监测系统

提出了一个新颖的数据流监测系统RealMon的设计和实现。该系统能够在大量的网络流量数据中通过分析不同数据流之间的关联关系及时地检测出数据异常。通过应用数据流挖掘算法,该系统能够对电信骨干网络的SNMP流量数据进行监测。同时为了解决所采集SNMP数据中存在着的大量数据质量问题,该系统集成了数据流清洗算法,该算法能够实时处理SNMP数据来提高所采集数据的质量。在模拟环境中的测试表明,该系统能够在SNMP数据流上同时对数千条链路进行有效监测。

分布式环境中数据库模式设计实践

近年来,数据规模呈爆炸式增长,使得传统集中式数据库难以满足业务需求.而分布式数据库可以将数据存储在多个节点上,具有更好的扩展性,从而可以支撑业务的不断增长.目前,许多企业已经开发出了成功的分布式数据库产品,例如Google Spanner、淘宝的OceanBase等.传统数据库模式设计中,三大范式(1NF、2NF和3NF)及其扩展范式能够减少数据冗余和更新异常,并保证数据的完整性.然而,在分布式架构下,严格遵循范式的模式设计可能带来查询效率较低等问题,而使用反范式模式设计方法通常可以有效提高查询效率.OceanBase是淘宝自主研发的分布式数据库,支持跨行跨表事务,并在OLTP中具有良好的性能,但是对于OLAP业务,其性能并不高.本文将以OceanBase为例,介绍如何利用反范式设计分布式数据库模式,以改善OLAP的查询性能,并通过在OceanBase上部署TPC-H基准评测验证了反范式模式设计的有效性和高效性.

微服务架构下访问控制模型的设计与实现

微服务架构降低应用模块之间的耦合度,有利于复杂应用系统的开发、部署和运维。但相比于单体应用其资源的访问控制也变得更加复杂。对微服务架构下的资源访问控制需求进行分析,提出一种基于角色的访问控制模型——MSAM(Microservice of Authority Management)。该模型具有对用户授予和屏蔽权限、数据权限和服务实例权限等特征,能够很好地满足微服务架构下的资源访问控制需求。讨论访问控制模型的实现,对比集中式鉴权与独立式鉴权两种实现的优缺点,说明不同实现方式所适用的场景。