计算机研究与发展杂志社
分享到:

计算机研究与发展杂志

《计算机研究与发展》杂志在全国影响力巨大,创刊于1958年,公开发行的月刊杂志。创刊以来,办刊质量和水平不断提高,主要栏目设置有:综述、计算机技术、计算机网络、人工智能、计算机软件、计算机应用等。
  • 主管单位:中科院出版委员会
  • 主办单位:中国科学院计算技术研究所
  • 国际刊号:1000-1239
  • 国内刊号:11-1777/TP
  • 出版地方:北京
  • 邮发代号:2-654
  • 创刊时间:1958
  • 发行周期:月刊
  • 期刊开本:A4
  • 复合影响因子:2.65
  • 综合影响因子:1.654
相关期刊
服务介绍

计算机研究与发展 2013年第S1期杂志 文档列表

XML查询中具有位置谓词的树模式匹配方法

摘要:XML树模式匹配是XPath查询等XML数据处理中的核心操作.采用整体匹配方式的XML树模式查询算法已经得到了深入研究,然而这些算法均未考虑到XPath表达式中位置谓词的实现需求.由于无法从整体匹配的结果中筛选出符合位置谓词的查询结果,使得这些算法无法用于实现具有位置谓词的XPath查询.为了支持具有位置谓词的XML树模式查询的实现,为XML树模式扩展了位置谓词和兄弟轴,提出了一种基于嵌套栈的整体模式匹配算法TwigPos,所实现的XPath查询能够同时支持存在谓词、位置谓词和兄弟轴.在不同数据集上的实验说明该算法能够有效地处理此类XML查询请求,增强了XML树模式查询技术的实用性.
1-11

前言

摘要:中国计算机学会数据库专委会举办的中国数据库学术年会(NDBC)为数据库及相关领域研究人员交流最新研究成果提供了一个很好的平台,经过多年的努力,已逐步成为在国内外学术界有一定影响力的数据库学术年会.第30届中国数据库学术会议(NDBC2013)将于2013年8月16日至2013年8月18日在冰城哈尔滨举行.本次会议由中国计算机学会主办,中国计算机学会数据库专业委员会协办,哈尔滨工程大学承办,支持单位包括黑龙江省计算机学会、哈尔滨工业大学、黑龙江大学、哈尔滨理工大学、哈尔滨师范大
7-7

面向XQuery语言的XML树模式识别方法

摘要:XML树模式查询(TPQ)是XML查询的核心操作,也是XML查询相关研究的热点.将XQuery语言描述的查询功能尽可能多地包含在XML树模式查询中,有助于提高XQuery程序的执行效率.面向一种扩展的XML树模式,用于实现XQuery语言的查询计划描述语言FXQL中扩展了XML树模式描述功能.同时,提出一种有效的XML树模式提取算法,能够从XQuery语言的for/let子句和return子句嵌套的FLWOR表达式中收集各种结构约束,并将这些结构约束合并成单个XML树模式,而不是基于传统提取算法的多个树模式.该方法扩大了XML树模式查询技术在XQuery语言实现中的应用范围,其算法实现和实验说明了该方法的有效性和实用性.
12-22

一种基于HBase的RDF数据存储模型

摘要:随着语义网数据的爆炸式增长,如何高效地管理海量RDF数据成为一个关键问题.现有的集中式关系型RDF数据存储管理系统已难以适应这种需求,越来越多的研究者使用分布式系统和并行计算技术来管理海量RDF数据.提出一种基于分布式数据库HBase的RDF数据存储模型,根据OWL本体定义文件,将数据按类划分,同一类的三元组数据保存在该类的S_PO和O_PS两张表中,实现该存储模型上的8种Triple Pattern和Basic Graph Pattern查询算法,并提供部分推理功能,在Hadoop集群环境下对存储模型与查询算法进行了可行性验证.
23-31

面向Twig查询的XML类型推导

摘要:Twig查询是XML数据查询的核心操作.在复杂的XML数据处理中,Twig查询结果的类型信息可以用于优化后续的XML数据查询与处理.针对这种情况,分析了Twig查询的类型推导问题,提出了一种精确的XML类型推导方法,能够根据Twig查询中的结构约束和输入数据的数据类型,推导出查询结果的精确类型,从而为作用于Twig查询结果的XML数据处理提供更加精确的XML类型信息,以支持更深入的静态类型检查和提供更多的类型相关的查询优化的机会.该方法包括XML模式图到XML类型树的转换、XML类型树上的Twig模式匹配、可共存类型节点判断和XML类型树的子类型化,以不同子类型化的XML类型树的形式为不同种类的Twig查询结果提供了精确的类型信息.实验说明了这种类型推导方法的有效性.
32-43

一种基于BPMN的业务流程图到BPEL的映射方法

摘要:随着服务组合理论的不断成熟,将基于BPMN的业务流程图转换为BPEL代码进而实现服务组合的研究受到广泛关注.目前BPMN模型的映射方法不能完成复杂结构的映射且需要人工参与.首先提出了一个基于服务组合的软件系统框架和BPMN的形式化描述方法.然后给出一种基于BPMN的业务流程图到BPEL的映射方法,其主要思想是首先映射数据流,再映射控制流来组织基本活动的执行顺序.在控制流映射中分析了基本结构和复杂结构映射的解决方案.最后,利用网上预约看病实例证明了映射方法的可行性.
44-52

含有丰富结构化数据的Web页面分类技术的研究

摘要:Web页面的主题识别和分类是垂直搜索引擎的核心,是结构化数据抽取的前提,具有重要的学术价值,工程应用也非常广泛.以往的工作多以定向爬虫技术来解决垂直搜索引擎数据采集的专业化问题,而Web页面的主题识别和分类也多采用传统的文本分类方法.针对含有丰富结构化数据的Web页面,提出了复用结构化数据抽取模板来进行Web页面主题识别的分类框架.该框架首先解析Web页面的组织结构,通过属性探测算法,获得Web页面所包含的主题关键词.进一步通过计算主题关键词与结构化抽取模板的相似性来判定Web页面的主题并按照领域进行分类.该方法避免了主题爬虫对URL格式严重依赖的问题,分类准确率也高于传统的文本分类方法.通过实验证明了框架在含有丰富结构化数据的Web页面分类方面的有效性.
53-60

递归树模式查询

摘要:XML作为半结构化数据描述语言在网络上应用广泛,而XQuery是专门针对XML数据的查询语言.在XQuery语言中,用户可以编写自定义递归函数对XML数据进行递归查询和处理,而如今被广泛研究的XML树模式查询是查询XML数据的核心操作.将自定义递归函数与树模式查询相结合可以使XQuery语言的实现获得更强大的查询描述和处理能力.扩展传统树模式查询提出了递归树模式查询的概念,并设计实现了递归树模式整体匹配算法.带有递归树模式的递归函数调用可以从递归树模式与XML文档的匹配结果中得到函数体表达式执行时所需的XML数据,其对XML数据源的查询次数随之大量减少,查询效率得到提高.实验结果表明,此方法可以有效地提高基于递归函数的XQuery查询效率.
61-69

查询性能预测方法的性能评测研究(英文)

摘要:目前的查询性能预测方法一般都是利用查询的特征、文档集合的特征以及结果列表的特征预测查询结果的平均精度(AP).一种性能预测方法与其他方法比较时,通常采用预测的AP和查询真实AP之间的皮尔森线性相关系数或是肯德尔等级相关系数来进行衡量.然而,这种简单比较方法往往不能准确评估预测方法的性能.深入探讨了查询性能预测方法性能评测中存在的问题,发现了影响比较公平性的4个因素:预测所基于的排序器、预测目标、评估指标以及实验的数据集合大小.并通过定量实验证明:1)排序器的检索性能越好,预测方法的预测性能也越好;2)不同的预测目标会影响预测性能,衡量搜索引擎质量指标(DCG)比AP更容易预测;3)相关性评估指标受数据分布影响严重,在相同的数据分布下,比较两种预测方法才公平;4)实验中查询集合过小会使得比较结果冲突,影响比较结果的可信度.本工作对查询性能预测方法的性能评测具有重要意义.
70-79

一个高效的连续k近邻查询改进算法

摘要:连续k近邻查询是空间数据库一直以来的热点问题.但大多数研究成果都是在欧式空间上的.IMA?GMA算法是少有的几种基于道路网的连续k近邻查询算法之一,同时也是比较优秀的算法.但是IMA算法仍然存在不足之处.在针对IMA算法的不足进行充分讨论后,提出了内结构迭代变更法和数据对象树,分别弥补了IMA在数据更新频繁和扩展树生成时表现出的性能缺陷.内结构迭代变更法在数据更新后对扩展树内结构进行快速调整,避免了对树的大规模剪枝以提高扩展树的利用率,从而提高在数据频繁更新时的性能.数据对象树用于快速获取子树上所有数据对象的有序集合,以辅助新查询利用已有查询的扩展子树结构.理论分析和仿真实验都证明了改进的IMA算法比原IMA算法更能适应多种情况,性能表现更为优异.
80-89

基于图的音乐数据查询处理及优化方法

摘要:音乐数据之间存在复杂关联关系,适合用图数据结构对其建模并进行查询处理.然而现有的图查询处理算法只关注图结构特征,并未针对音乐元数据和音乐内容数据进行优化,查询效率不高.基于图音乐数据模型GraMM与查询语言GraMQL,提出了基于图的音乐数据查询处理算法.该算法根据音乐数据的特点,使用图结构剪枝、音乐元数据剪枝以及音乐内容剪枝3种策略对搜索空间进行剪枝,提高了查询效率.进而给出了调整查询顶点搜索顺序的优化方法以及基于开销模型的音乐内容剪枝位置优化方法,加快了查询处理速度.实验结果表明所提音乐查询处理及优化算法能高效处理音乐元数据和音乐内容数据查询请求.
90-100

一种基于压缩策略的高维空间子空间skyline查询算法

摘要:skyline操作就是找出数据集中不被其他数据点支配的点的集合,但是随着数据属性维度的不断增多,通常人们只对数据集的某几个属性感兴趣,高维空间子空间skyline计算就是发现数据集中在某几个特定维度上不被其他点支配的点的集合,skyline计算在数据量大时其时间花销是非常大的,快速的返回结果才是人们能接受的.基于此提出了一个RSky算法,在原有CSky算法的基础上,指出并改进了其存在的3处明显不足,并根据InvertS索引的特性提出了一个压缩扫描策略,通过设置每个维度的下限来控制要处理的桶,除去不必要处理的桶和不可能是skyline的点,从而减少了点与点之间的比较次数.实验结果表明了RSky算法的有效性.
101-108

含排他性选择规则的主动规则集的汇流性判定方法

摘要:主动规则已经应用于主动数据库、XML文档和语义网络等领域,主动规则集的汇流性维护了数据库的数据一致性、保证了数据质量,但现有方法不能有效地判定主动规则集的汇流性.现有的方法基于规则可交换性进行判定,但只是针对指定了优先级的规则集,对没有指定优先级的规则集的汇流性没有相应的判定方法;同时也没有考虑在同一个初始状态下,不同的规则调度是否都能被条件满足.为此,提出了排他性选择规则的概念和更有效的汇流性先决条件及其汇流判定定理.同时给出了新的判定算法的完整描述及其可终止性、正确性证明和复杂度分析.
109-116

Attribute-or模型下不确定关系的无损分解算法

摘要:庞大的可能世界集合是影响不确定关系查询效率的主要因素,分解是减小不确定关系可能世界集合的有效方法.为解决该问题,在Attribute-or数据模型上,定义了水平函数依赖和垂直函数依赖.提出了不确定关系水平划分算法,该算法能够生成不确定关系的分解条件,解决了分解程度低的问题.给出了不确定关系分解过程和算法并证明该分解方法是无损的,讨论了k-匿名数据的分解问题.
117-124

面向属性级不确定数据的U-Topk查询优化算法的研究

摘要:U-Topk是基于不确定性数据可能世界模型而提出的一种查询语义.随着不确定性数据集的增大,可能世界的实例数量指数增长,这为U-Topk查询处理提出了重大挑战.针对属性级不确定性的UTopk查询处理算法展开研究,提出了U-Topk查询处理优化算法APT4U-Topk.首先通过预处理来确定必然进入最终结果集的元组,从而实现k值的压缩.然后,依次读取后续元组,计算可能世界模型聚合概率,并判断此时刻是否为可能世界模型聚合概率的阈值.当到达阈值时算法停止.此时概率最大的聚合可能世界模型就是U-Topk查询结果.最后,通过实验对APT4U-Topk算法进行了时空效率的验证.实验结果表明,在数据集和k值增大的情况下,APT4U-Topk算法要优于此前提出的OptU-Topk算法.
125-132

科学工作流中面向不确定数据源图的受限可达查询

摘要:在现代分布式网络环境中开发与应用科学工作流系统时,由于受数据采集的准确度和网络链路可靠性影响,将会导致工作流运行中所产生数据源图的不确定性,在这样的不确定式数据源图中进行面向工作流任务的概率式受限可达查询时将面临着新的技术挑战.针对此问题提出了一种紧凑有效的概率式受限可达查询算法,用于解决不确定数据源图中任意两点间受限于特定任务集的概率可达查询;并提出了一种基于扩展树的数据结构,用于计算数据源图中任意两节点间的可达查询,并给出所有可达路径,然后根据容斥原理对已知可达路径的可达概率计算进行简化;最后给出实验对算法的特点进行评估与分析.
133-144

无线数据广播环境下的空间关键字查询

摘要:在移动计算环境下,无线数据广播是一种可拓展性强、节能、适合用户数量大的信息技术.提出了一个在无线数据广播环境下支持空间关键字检索的框架,并提出了一种基于网格索引与倒排表结合的空中索引:IRGI(information retrieval grid index).IRGI的优点是:1)相对文档的大小,索引本身很小,因此可以在一个周期内分布多次索引,以降低访问延迟,增强用户体验效果;2)通过网格索引和倒排表,用户可以剪枝落在区域外的或者不包含感兴趣关键字的文档,从而使用户保持监听状态的时间大大减小,降低能量消耗.最后通过人工生成的数据和真实地图的数据进行了实验模拟,实验结果证明了该方法不但访问延迟低,而且能量消耗小.
145-153

基于结构-属性的时空对象图聚类算法的研究

摘要:在现有的图聚类方法中,大多数聚类方法只关注图的拓扑结构或节点属性而忽略另一方面.为解决这一问题,相关文献中提出了基于图的结构与属性的图聚类方法.但这些聚类方法存在建立的图模型不准确、聚类效果不理想、算法执行效率低等缺点.针对上述图聚类方法中存在的问题,提出了一种基于结构-属性的时空对象图聚类方法(spatio-temporal object graph clustering algorithm based on structure and attribute,STSA).首先提出了属性加权图模型,在此基础上建立了结构-属性的统一度量方法,并采用随机游走模型技术将节点间结构与属性关系转换为相应的相似度矩阵,结合图结构-属性关系及相似度矩阵,采用信息传递算法对图进行聚类,解决了现有图聚类方法中所存在的问题,最后通过实验验证了提出的STSA方法的正确性和有效性.
154-162