计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2011年第10期杂志 文档列表

计算机学报杂志海量数据管理架构和处理算法

架构大数据：挑战、现状与展望1741-1752

摘要：大数据分析相比于传统的数据仓库应用,具有数据量大、查询分析复杂等特点.为了设计适合大数据分析的数据仓库架构,文中列举了大数据分析平台需要具备的几个重要特性,对当前的主流实现平台——并行数据库、MapReduce及基于两者的混合架构进行了分析归纳,指出了各自的优势及不足,同时也对各个方向的研究现状及作者在大数据分析方面的努力进行了介绍,对未来研究做了展望.

云计算环境下的大规模图数据处理技术1753-1767

摘要：随着社交网络分析、语义Web分析、生物信息网络分析等新兴应用的快速增长,对亿万个顶点级别大规模图的处理能力的需求愈加迫切,这是当前高性能计算领域的研究和开发热点.文中结合云计算的特点,从图数据管理与图数据处理机制两个方面,综述了云计算环境下进行大规模图数据处理的关键问题,包括图数据的存储方式、图索引结构、图分割策略、图计算模型、消息通信机制、容错管理、可伸缩性、图查询处理等.全面总结了当前的研究现状和进展,详细分析了存在的挑战性问题,并深入探讨了未来的研究方向.

基于消息传递机制的MapReduce图算法研究1768-1784

摘要：单机运行环境难以满足基于海量数据的大图算法对时空开销的需求,如何设计高效的面向云计算环境的分布式大图算法越来越受到人们的关注,MapReduce作为云计算的核心计算模式受限于易并行（EP）计算模型的制约不易表达图算法.文中突破了MapReduce基于易并行计算的假设,增强了MapReduce既有的编程规范,新的大同步（BSP）计算模型既能保证兼容旧的MapReduce作业可以无改动的运行,同时引入消息传递机制允许变化的状态数据在并行任务的超级步间进行交互.系统提供高度灵活的消息自定义接口,针对不同应用需求设计了轻量级和重量级两种自适应的消息传递机制,更高效地支持有数据交互需求的包含迭代处理的一大类图算法.在真实大规模图数据集上的实验结果表明,相比于原始的MapReduce作业外部链式处理,该文提出的BSP模型下的内部超级步迭代计算模式大幅降低了大图算法的处理时间.

基于Map-Reduce的海量数据高效Skyline查询处理1785-1796

摘要：Skyline查询已成为现今数据库和信息检索领域的研究热点之一,伴随着人类可以采集和利用的数据信息的急剧增长,使得如何处理海量数据的Skyline查询成为急需解决的问题.近年来兴起的Map-Reduce编程框架能够有效地处理基于海量数据的应用,该文既是研究如何运用Map-Reduce编程框架解决海量数据的Skyline查询问题.在Map-Reduce框架下处理Skyline查询的直接方法是扫描整个数据集进而得到查询结果,但是在海量数据Skyline查询问题中,查询结果的数量远小于原始数据集的数据量,对此该文提出了一系列的Skyline查询算法及优化,有效地过滤掉部分不能成为Skyline查询结果的数据对象,大幅度提高了在Map-Reduce框架下处理Skyline查询的效率.大量运行在Hadoop平台上的实验验证了该文所提出的Skyline查询处理算法具有良好的有效性、准确性和可用性.

计算机学报杂志海量数据应用

基于关键词的深度万维网数据库选择1797-1804

摘要：该文提出一种基于关键词的深度万维网查询方法：用户用关键词的方式提交查询,该方法在线地选择能够反映查询意图并且提供高质量结果的万维网数据库.这种方法既避免了深度万维网数据抓取这一代价高、难度大的操作,又可支持多领域的数据库上的关键词查询,从而能够与现有的搜索引擎实现无缝集成.文中侧重于讨论基于关键词的数据库选择,从以下两个方面解决这一问题所涉及的挑战：（1）提出了一种度量关键词-领域属性关联的相关性模型,并设计了基于随机游动的算法从查询日志中发现潜在的关键词-属性关联;（2）给出了一种新的数据采样方法,并用于基于采样的数据库-查询的相关性模型中,最终解决深度万维网的数据库选择问题.在中文深度万维网真实数据集上的实验表明：提出的方法能够有效地选择与关键词查询相关的数据库,提供高质量的结果.

计算广告：以数据为核心的Web综合应用1805-1819

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

轨迹隐私保护技术研究1820-1830

摘要：随着移动设备和定位技术的发展,产生了大量的移动对象轨迹数据.轨迹数据含有丰富的时空信息,对其分析和挖掘可以支持多种与移动对象相关的应用.然而,针对轨迹数据的攻击性推理可能导致个人的兴趣爱好、行为模式、社会习惯等隐私信息暴露.另一方面,在基于位置的服务中,由于现有位置隐私保护技术并不能解决轨迹隐私泄露的问题,移动对象的个人隐私很可能通过实时运行轨迹而暴露.针对上述两种场景,轨迹隐私保护的研究提出了明确的要求：在轨迹数据中,隐私保护技术既要保护轨迹数据的隐私,又要保证数据有较高的可用性;在基于位置的服务中,隐私保护技术既要保护移动对象的实时轨迹隐私,又要保证用户获得较高的服务质量.该文针对上述两个问题分析了轨迹隐私保护中存在的挑战性问题,针对不同的隐私保护方法分析了现有的研究工作,介绍了当前该领域的研究热点,指明了未来的研究方向.

干预规则挖掘的概念、任务与研究进展1831-1842

摘要：干预规则挖掘是近年从干预实践中提出的新型数据挖掘任务,旨在利用数据挖掘技术探测干预事件,发现最佳干预时机和力度,提供促进事物向期待状态转化的决策支持.文中以四年的研究实践为背景,介绍干预规则挖掘的研究沿革和现状,给出了干预规则挖掘的任务分类.从三个角度,即干预效果预测、干预方法发现和未知干预探测三方面,介绍干预规则挖掘的研究问题、困难和成果.展望了干预规则挖掘未来研究方向.

计算机学报杂志海量数据处理关键技术

复杂数据上的实体识别技术研究1843-1852

摘要：复杂数据当前有着广泛的应用.有效地使用复杂数据需要对其质量进行管理.实体识别是数据质量管理的基本操作,用于在数据集合中发现同一实体的不同描述,其在数据质量管理中可以用于错误检测、不一致数据发现等.由于包含复杂的结构信息,复杂数据上的实体识别与传统文本和关系数据上的实体识别不同,带来了新的技术上的挑战.该文介绍了复杂数据上实体识别的概念和应用,分别讨论了XML数据、图数据和复杂网络上实体识别技术的原理,最后展望了未来的研究方向.

集合和字符串的相似度查询1853-1862

摘要：相似度查询是计算机学科中一个重要的问题,它的应用遍及多个领域,例如数据库、数据集成、互联网、数据挖掘以及生物信息学等.该文主要讨论在集合和字符串上的相似度查询.学术界从2000年来在这个领域内取得了大量的进展.作者总结了主要工作,并给出了作者的分析和归类.最后,该文提出了一些未来工作的方向.

一种优化关系型溯源信息存储的新方法1863-1875

摘要：现代数据管理必须处理来源不同、质量各异的数据,因此从系统层面支持数据溯源,让用户了解数据的来源及派生过程成为当前至关重要的一个研究课题.基于标注的方法是支持数据溯源的基本方法之一.这种方法的主要问题是存储空间开销,因为溯源信息可能会超过实际数据的大小.在该文中,作者提出了一个用与查询结构匹配的溯源树来表达和存储溯源信息从而避免数据派生过程中冗余存储的基本框架.基于这个框架,作者提出了一系列针对关系型查询的存储优化方法,选择查询树部分节点来存储溯源信息.这些优化算法对于查询大小是多项式时间,对于溯源信息大小是线性时间,在溯源信息的跟踪和优化方面均不会产生巨大的开销.这一框架是数据溯源研究的一个新思路,有着广泛的应用前景.

计算机学报杂志数据库年会优秀论文

一种ρ-支配轮廓查询的高效处理算法1876-1884

摘要：近年来,作为重要的多目标决策手段的轮廓查询逐渐得到学术界的重视,相继提出了基于不同支配关系的多种轮廓变体查询.首先,通过对实际应用需求进行分析,提出了基于元组对应数值间比例值大小的ρ-支配关系的定义,进而提出了ρ-支配轮廓查询的概念.其次,对ρ-支配轮廓的基本性质进行了细致而深入的分析,在此基础上,提出了基于分支定界的ρ-支配轮廓查询算法（Branch and Boundρ-Dominant Skyline Algorithm,BBDS）,避免了对R-树索引的多次访问,从而提高了ρ-支配轮廓查询的执行效率.最后,通过大量的仿真实验对ρ-支配轮廓查询的语义进行分析,并对BBDS算法的性能进行验证.实验结果表明,ρ-支配轮廓查询是轮廓查询语义的扩展和补充,而提出的BBDS算法则是求解ρ-支配轮廓查询的高效算法.

不确定图上的高效top-k近邻查询处理算法1885-1896

摘要：图的不确定性普遍存在,研究不确定图的高效查询处理具有重要意义.文中提出了不确定图上一种新型查询——近邻查询.给定一个查询标签集R和距离约束σ,在不确定图G上进行近邻查询是要找到标签集包含R并且任意两个顶点间距离不超过σ的匹配顶点集.为解决该问题,文中首先提出了＂可靠期望距离＂,然后基于可靠期望距离建立了高效的近邻关系图索引,将不确定图上的近邻查询等价地转化为近邻关系图上的团查询问题,最后使用树搜索算法解决近邻关系图上的团查询问题.理论分析和实验结果表明文中提出的算法能够高效地完成不确定图上的top-k近邻查询.

一种基于概率图模型的不确定性数据世系表示方法1897-1906

摘要：不确定性数据的世系分析是基于数据产生和演变的过程来跟踪数据不确定性的来源.为了有效地描述数据间复杂的相关性及不确定性,并从理论上保证世系分析中概率计算的正确性,文中研究了基于贝叶斯网这一重要的概率图模型的不确定性数据世系表示方法.以世系的布尔公式和不确定性数据本身为出发点,提出了将布尔公式等价转换为贝叶斯网的方法,并讨论了相应的条件独立性质和概率语义.案例研究和实验结果表明,文中的方法为世系分析提供了一种有效性的、可扩展的数据相关性表示和概率计算框架.

入侵容忍实时数据库的半马尔可夫生存能力评价模型1907-1916

摘要：针对事务和数据的实时特性,给出了具有入侵容忍能力的实时数据库系统的体系架构.基于实时性的要求和入侵检测存在的延迟,提出了半马尔可夫评价模型,对实时数据库在入侵容忍条件下的生存能力进行评价,并根据此模型给出相关的量化准则,定义了完整性与可用性等生存性指标,对实时数据库的生存能力进行了验证.由于误报、检出率和攻击强度等因素会对生存能力造成重大影响,因此利用TPC-C基准测试对其进行了详细的数据分析.实验表明,该模型能较准确地预测实时数据库的行为,所提出的入侵容忍实时数据库在面临攻击时,其基本生存能力没有受到严重的影响.

一种障碍空间中的反k最近邻查询方法1917-1925

摘要：随着基于位置的服务（LBS）和物联网的快速发展,空间查询技术越来越重要,而空间查询中的最近邻查询及其各种变体有着广泛的应用.近几年,已有较多对于查询前k个反最近邻对象（RkNN）的研究,其中大部分针对的都是理想欧氏空间.而在真实的情况下,反k最近邻查询通常受障碍物影响.文中研究了障碍空间中反k最近邻查询算法,提出了一种基于障碍Voronoi图的高效的剪枝方法.根据Voronoi图和障碍距离的特性,大幅度减少了数据点处理个数.最后,作者使用真实的数据集和多种方式分布的模拟数据,验证了算法的高效性和准确性.

基于星型模式的一个多路top-k join算法1926-1935

摘要：top-kjoin查询返回用户最感兴趣的k个连接结果.近来top-kjoin已经成为一个重要的研究课题,且在Web数据库、信息抽取和数据挖掘中均有应用.星型模式的数据仓库在实际应用中也存在top-kjoin查询,如有时决策者只想查询星型连接结果中他最感兴趣的k个.然而,现有top-kjoin算法不适合星型模式.为了在星型模式上有效地支持top-kjoin查询,文中提出两类索引并基于这两类索引提出一个适用于星型模式的多路top-kjoin算法.该算法通过采用一个比现有算法更优的上界和一个剪枝策略获得了更高的效率.此外,实验也表明文中的算法比现有算法效率更高.

海量数据分析的One-size-fits-all OLAP技术1936-1946

摘要：传统的OLAP被迅速膨胀的海量数据推动进入了大规模数据分析时代,其主要特点是存储密度大,计算强度大,需要大规模并行存储和处理能力.无论是传统的并行数据库技术还是热点的MapReduce技术都不得不面对海量数据在大规模并行处理环境下的性能和并行处理效率的问题.以星型模型上复杂多表连接为基础的OLAP算法的复杂度和并行处理过程中的数据网络传输代价都成为制约性能的重要因素.通过深入分析OLAP存储模型和查询负载特征,提出了对OLAP查询中最基础的SPJGA-OLAP子集在存储、查询处理、数据分布、网络传输和分布式缓存等方面面向海量数据大规模并行处理框架的优化策略和实现技术.通过对TPC-H和SSB两个工业界和学术界公认的测试标准的分析,评估了技术的可行性.提出了以内存predicate-vector DDTA-JOIN算法为核心的并行内存OLAP架构,以维表上规范化的谓词向量操作替代了多样的连接执行计划,实现以一种查询处理模型同时满足集中式处理和大规模并行OLAP处理的需求,充分利用现代计算机的硬件优势,最小化网络传输和OLAP查询处理代价.实验中分析了在1TB和100TB数据集中数据分布策略的存储代价和传输代价,通过并行OLAP代价模型和实际数据的实验测试验证了技术的可行性和并行处理效率.