2008, 19(2):179-193.
摘要:Web数据库中,海量的信息隐藏在具有特定查询能力的查询接口后面,使人无法了解一个Web数据库内容的特征,比如主题的分布、更新的频率等,这就为Deep Web数据集成带来了巨大的挑战.为了解决这个问题,提出了一种基于图模型的Web数据库采样方法,可以通过查询接口从Web数据库中以增量的方式获取近似随机的样本,即每次查询获取一定数量的样本记录,并且利用已经保存在本地的样本记录生成下一次的查询.该方法的一个重要特点是不受查询接口中属性表现形式的局限,因此是一种一般的Web数据库采样方法.在本地的模拟实验和真实Web数据库上的大量实验表明,该方法可以在较小代价下获得高质量的样本.
2008, 19(2):194-208.
摘要:分析了常见的实体识别方法,提出了一种基于语义及统计分析的实体识别机制(deep Web entity identification mechanism based on semantics and statistical analysis,简称SS-EIM),能够有效解决Deep Web数据集成中数据纠错、消重及整合等问题.SS-EIM主要由文本匹配模型、语义分析模型和分组统计模型组成,采用文本粗略匹配、表象关联关系获取以及分组统计分析的三段式逐步求精策略,基于文本特征、语义信息及约束规则来不断精化识别结果;根据可获取的有限的实例信息,采用静态分析、动态协调相结合的自适应知识维护策略,构建和完善表象关联知识库,以适应Web数据的动态性并保证表象关联知识的完备性.通过实验验证了SS-EIM中所采用的关键技术的可行性和有效性.
2008, 19(2):209-223.
摘要:当前,Web上的很多网页是动态生成的,网站根据请求从后台数据库中选取数据并嵌入到通用的模板中,例如电子商务网站的商品描述网页.研究如何从这类由模板生成的网页中检测出其背后的模板,并将嵌入的数据(例如商品名称、价格等等)自动地抽取出来.给出了模板检测问题的形式化描述,并深入分析模板产生网页的结构特征.提出了一种新颖的模板检测方法,并利用检测出的模板自动地从实例网页中抽取数据.与其他已有方法相比,该方法能够适用于"列表页面"和"详细页面"两种类型的网页.在两个第三方的测试集上进行了实验,结果表明,该方法具有很高的抽取准确率.
2008, 19(2):224-236.
摘要:提出了一种基于词频统计的方法以估算Web数据库的规模.通过分析Web数据库查询接口中属性之间的相关度来获取某个属性上的一组随机样本;并对该属性分别提交由前k位高频词形成的试探查询以估算Web数据库中记录的总数.通过在几个真实的Web数据库上进行实验验证,说明该方法可以准确地估算出Web数据库的大小.
2008, 19(2):237-245.
摘要:借鉴语义Web领域中深度标注的思想,提出了一种对Web数据库查询结果进行语义标注的方法.为了获得完整且一致的标注结果,将领域本体作为Web数据库遵循的全局模式引入到查询结果语义标注过程中.对查询接口及查询结果特征进行详细分析,并采用查询条件重置的策略,从而确定查询结果数据的语义标记.通过对多个不同领域Web数据库的测试,在具有领域本体支持的条件下,该方法能够对Web数据库查询结果添加正确的语义标记,从而验证了该方法的有效性.
2008, 19(2):246-256.
摘要:在深度网研究领域,通用搜索引擎(比如Google和Yahoo)具有许多不足之处:它们各自所能覆盖的数据量与整个深度网数据总量的比值小于1/3;与表层网中的情况不同,几个搜索引擎相结合所能覆盖的数据量基本没有发生变化.许多深度网站点能够提供大量高质量的信息,并且,深度网正在逐渐成为一个最重要的信息资源.提出了一个三分类器的框架,用于自动识别特定领域的深度网入口.查询接口得到以后,可以将它们进行集成,然后将一个统一的接口提交给用户以方便他们查询信息.通过8组大规模的实验,验证了所提出的方法可以准确高效地发现特定领域的深度网入口.
2008, 19(2):257-266.
摘要:研究了Deep Web集成环境中构件的依赖关系(执行偏序依赖和知识依赖),并在此基础上提出了一种基于知识的环境变化的处理方法,包括Deep Web集成环境变化处理模型以及适应Deep Web环境变化的动态体系结构和处理算法,可以对大规模Deep Web集成的进一步探索和走向应用提供参考.实验结果表明,该方法不仅可以处理Deep Web环境的变化,还可以大幅度提高集成系统的性能.
2008, 19(2):267-274.
摘要:讨论了提高Deep Web数据库分类准确性的若干新技术,其中包括利用HTML网页的内容文本作为理解数据库内容的上下文和把数据库表的属性标记词归一的过程.其中对网页中的内容文本的发现算法是基于对网页文本块的多种统计特征.而对数据库属性标记词的归一过程是把同义标记词用代表词进行替代的过程.给出了采用分层模糊集合对给定学习实例所发现的领域和语言知识进行表示和基于这些知识对标记词归一化算法.基于上述预处理,给出了计算Deep Web数据库的K-NN(k nearest neighbors)分类算法,其中对数据库之间语义距离计算综合了数据库表之间和含有数据库表的网页的内容文本之间的语义距离.分类实验给出算法对未预处理的网页和经过预处理后的网页在数据库分类精度、查全率和综合F1等测度上的分类结果比较.
2008, 19(2):275-290.
摘要:提出了基于页面Block对Web页面的采集和存储方式,并详细表述了该方法如何完成基于布局页面分区、Block主题的抽取、版本和差异的比较以及增量存储的方式.实现了一个Web归档原型系统,并对所提出的算法进行了详细的测试.理论和实验表明,所提出的基于页面Block的Web档案(Web archive)采集和存储方法能够很好地适应Web档案的管理方式,并对基于Web档案的查询、搜索、知识发现和数据挖掘等应用提供有利的数据资源.
2008, 19(2):291-300.
摘要:目前,查询性能预测(predicting query performance,简称PQP)已经被认为是检索系统最重要的功能之一.近几年的研究和实验表明,PQP技术在文本检索领域有着广阔的发展前景和拓展空间.对文本检索中的PQP进行综述,重点论述其主要方法和关键技术.首先介绍了常用的实验语料和评价体系;然后介绍了影响查询性能的各方面因素;之后,按照基于检索前和检索后的分类体系概述了目前主要的PQP方法;简介了PQP在几个方面的应用;最后讨论了PQP所面临的一些挑战.
2008, 19(2):301-313.
摘要:通过基于主动决策引擎日志的数据挖掘来找到分析规则的CUBE使用模式,从而为多维数据实视图选择算法提供重要依据;在此基础上设计了3A概率模型,并给出考虑CUBE受访概率分布的视图选择贪婪算法PGreedy (probability greedy),以及结合视图挽留原则的视图动态调整算法.实验结果表明,在实时主动数据仓库环境下,PGreedy算法比BPUS(benefit per unit space)算法具有更好的性能.
2008, 19(2):314-322.
摘要:针对数据共享环境多数据源选择MDSS(multiple data sources selection)问题,基于Pareto最优理论提出了MDSSA(MDSS algorithm)算法.该算法借助崭新的基于法线测量的非线性路径代价方程计算出到每个数据源的最优路径集合,进而通过代价对比确定实施数据访问的最佳数据源及路径,极大地缩小了搜索空间,在搜索到有效路径的同时,确保了算法的响应时间.大量仿真实验表明,MDSSA算法是有效的.
2008, 19(2):323-337.
摘要:提出一种基于数据库模式的数据库关键词检索结果展现方法S-CBR(schema-based classification, browsing and retrieving),包括结果分类、用户浏览和再次检索3个过程.S-CBR首先利用数据库模式和查询关键词自动产生第一级类别,将检索结果分配到各个类中;对于比较大的类,按关键词节点内容进行第二级分类;另外赋给每个类别一个类别描述,并将类别描述和每个结果图形化地展现出来,使用户容易阅读和理解检索结果.用户还可以根据S-CBR提供的结果类别模式信息对感兴趣的类别作进一步检索,以尽快找到所需结果或获取更多的相关结果.实验证明了S-CBR方法的有效性.
2008, 19(2):338-350.
摘要:在拓展现有反向频繁挖掘问题定义,探索反向频繁项集的3个具体应用后,提出了一种基于FP-tree的反向频繁项集挖掘方法.该方法首先采用分治思想,将目标约束划分为若干子约束,每步求解一个子线性约束问题,经过若干步迭代后找到一个满足整个给定约束的目标FP-tree;然后根据目标FP-tree生成一个仅含频繁项的临时事务数据库TempD;最后通过向TempD中撒入非频繁项得到目标数据集.理论分析和实验表明该方法是正确的、高效的,且与现有方法仅能输出1个目标数据集相比,该方法能够输出较多的目标数据集.
2008, 19(2):358-368.
摘要:提出了一种SVM+BiHMM的混合元数据自动抽取方法.该方法基于SVM(support vector machine)和二元HMM(bigram HMM(hidden Markov model),简称BiHMM)理论.二元HMM模型BiHMM在保持模型结构不变的前提下,通过区分首发概率和状态内部发射概率,修改了HMM发射概率计算模型.在SVM+BiHMM复合模型中,首先根据规则把论文粗分为论文头、正文以及引文部分,然后建立SVM模型把文本块划分为元数据子类,接着采用Sigmoid双弯曲函数把SVM分类结果用于拟合调整BiHMM模型的单词发射概率,最后用复合模型进行元数据抽取.SVM方法有效考虑了块间联系,BiHMM模型充分考虑了单词在状态内部的位置信息,二者的元数据抽取结果得到了很好的互补和修正,实验评测结果表明,SVM+BiHMM算法的抽取效果优于其他方法.
2008, 19(2):361-357.
摘要:包括计数算子在内的属性构造技术往往能够提高数据挖掘模型的预测精度,但不加条件地使用会导致属性关系不一致问题.为解决此问题,在提出了属性关系一致等3个属性构造原则后,给出了在时序相关模型下避免属性关系不一致问题的新算法——时序计数算子.时序增量计数算子在满足其假设条件下,可以较小的代价显著地降低时序计数算子的高计算成本.实验结果验证了上述结论.
2008, 19(2):369-378.
摘要:在Web应用环境中,可以通过RDF(S)形式描述企业领域内分布信息资源的语义,以提高信息查询的准确性.提出了描述分布异构RDF(S)的分布RDF(S)模型,并基于这一模型给出了实现分布RDF(S)查询的方法,此查询方法既能实现实例层次的查询,也能实现概念层次的查询.基于这一方法,用户能够以统一的形式来查询,获取相关的信息资源,同时还可以实现分布RDF(S)的集成.
2008, 19(2):379-388.
摘要:通过对一些著名的闭合频繁集挖掘算法(如CLOSET+, FP-CLOSE,DCI-CLOSED和LCMv2等)的研究并结合挖掘理论分析,提出了一种新的挖掘算法Cherry,它基于FP-tree结构,并采用了新颖的Cherry Item检测技术,无须在内存中保留闭合频繁集而直接检测出会导致重复的频繁项前缀,从而极大地提高了挖掘效率.性能实验的比较和测试表明,该Cherry算法在低支持度的测试中要优于目前的一些主流挖掘算法,如LCMv2,DCI-CLOSE和FP-CLOSE等.
2008, 19(2):389-403.
摘要:在无线传感器网络体系结构中,MAC(medium access control)协议是保证网络高效通信的重要协议.无线传感器网络有着与传统无线网络明显不同的性能特点和技术要求,传统无线网络MAC协议无法应用于传感器网络,各种针对特定传感器网络特点的MAC协议相继提出.归纳无线传感器网络MAC协议的设计原则和分类方法,分析当前典型的各类MAC协议的主要机制,详细比较这些协议的特点、性能差异和应用范围.最后总结无线传感器网络MAC协议的研究现状,指出未来的研究重点.
2008, 19(2):404-418.
摘要:P2P系统在Internet上的成功使研究者关注于分布式更强、参与性更广、更具有对等自治特征的移动网络环境.智能终端的普及和移动应用环境的逐渐成熟使得移动对等网络拥有广阔的发展前景.但当前对移动对等网络的研究还缺乏统一而明确的定义,还存在很多未能很好地解决的问题.首先,概述了移动对等网络的基本概念,给出了其定义、特征以及与移动Ad Hoc网络的区别,并指出了移动对等网络的相关关键技术;随后,详细综述了移动对等网络体系结构、资源搜索策略、网络结构一致性、数据分发策略、安全与隐私机制等关键技术的研究现状,对各种关键技术的研究成果给出了深入分析,并指出了各自存在的问题和缺陷.最后,讨论了移动对等网络未来的研究方向和发展趋势.
2008, 19(2):419-431.
摘要:ISP(Internet service providers)和企业部署网络监测系统以获取网络的性能数据,确保网络的安全性和连通性,最终加强和改善全局的网络性能.网络监测系统的设计和优化是目前的一个研究热点,其优化目标是最小化监测系统的部署代价和维护代价,并使得对网络的影响尽可能地小.根据测量方式和收集框架的不同,可以设计出不同的网络测量部署模型.这些模型的最优化问题通常是NP难的,一般采用整数规划、设计近似算法和映射到经典优化问题等方法来求取模型的优化解.总结了网络测量部署模型及其优化算法的研究现状,指出了该领域中需要进一步研究的热点问题.
2008, 19(2):432-445.
摘要:当前普遍采用的复制技术和事务处理技术都无法满足应用的End-to-End可靠性需求,前者通过前向错误恢复来保证应用操作的存活性,后者通过后向错误恢复来保证应用数据的安全性.如何融合这两种技术以实现End-to-End可靠性保证,成为目前研究的热点问题.然而,已有的方法都是基于简单事务模式的假设,即只有中间层应用服务器上的容器发起事务,而很少考虑应用中普遍存在的复杂事务模式,如客户事务和嵌套事务.为了解决这个问题,首先识别出了几种典型的事务模式.针对这些事务模式,基于状态同步点概念提出了一种能够统一提供End-to-End可靠性保证的Web应用服务器复制机制RSCTP(replication scheme for complex transaction pattern).RSCTP机制采取primary-backup方式来复制EJB组件以保证业务逻辑的高可用性,同时采取primary-backup方式复制事务协调者来消除分布式事务处理中两阶段提交协议可能出现的阻塞问题.通过在不同事务模式下的失效分析,说明了该机制的有效性.已经实现了RSCTP机制并集成到了遵循J2EE规范的Web应用服务器OnceAS中.性能评价显示,该机制带来的系统开销较小.
2008, 19(2):446-454.
摘要:提出了一种普遍适用于网格拓扑压缩的高效熵编码方法.不同于以往的单纯利用算术编码或Huffman编码对遍历网格生成的拓扑流进行编码压缩,对这些拓扑流的每个符号先计算其Huffman编码,然后采用基于上下文(已编码序列的倒数第2个符号作为上下文)的算术编码方法来编码其Huffman值,从而实现对网格模型拓扑信息的有效压缩.实验结果表明,熵编码方法普遍适用于各种网格拓扑压缩方法得到的拓扑流的压缩,其压缩结果普遍高于拓扑流序列的熵值——绝大多数拓扑压缩算法各自最好的压缩比.
2008, 19(2):455-467.
摘要:首先,根据ROI(region of interest)面积给出了充分三重覆盖此ROI所需要的信标发射位置数量计算方法;接着,针对矩形ROI提出了一种简单的信标发射位置确定方法;之后,针对任意形状ROI提出了利用虚拟力获取信标发射位置坐标的方法;最后,利用流浪旅行商算法获取遍历这些发射位置点的最优路径,并基于多边测量方法进行传感器节点定位.仿真实验表明,采用上述方法可以对传感器节点进行高效且精度可控的定位.
2008, 19(2):468-478.
摘要:提出了一种从3轮公开掷币的对任何NP语言的诚实验证者零知识证明系统到纯公钥模型下4轮(轮最优)对同一语言的具有并发合理性的并发零知识证明系统.该转化方法有如下优点:1) 它只引起O(1)(常数个)额外的模指数运算,相比Di Crescenzo等人在ICALP 05上提出的需要((n)个额外的模指数运算的转化方法,该系统在效率上有着本质上的提高,而所需的困难性假设不变;2) 在离散对数假设下,该转化方法产生一个完美零知识证明系统.注意到Di Crescenzo等人提出的系统只具有计算零知识性质.该转化方法依赖于一个特殊的对承诺中的离散对数的3轮诚实验证者零知识的证明系统.构造了两个基于不同承诺方案的只需要常数个模指数运算的系统,这种系统可能有着独立价值.