软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2009年第07期杂志 文档列表

软件学报杂志模式识别与人工智能

基于智能体的多目标社会进化算法1703-1713

摘要：提出了一种基于智能体的多目标社会进化算法用以求解多目标优化问题（multiobjective optimization problems，简称MOPs），通过多智能体进化的思想来完成Pareto解集的寻优过程．该方法定义可信任度来表示智能体间的历史活动信息，并据此确定智能体的邻域、控制智能体间的行为．针对多目标问题的特点，设计了3个进化算子分别体现适者生存、弱肉强食、多样性原则以及自学习的特性．同时采用擂台赛法则构造Pareto解的存储种群．仿真实验结果表明，该算法能够较好地收敛到Pareto最优解集上，并且具有良好的多样性．另外，通过对智能体局部邻域环境建立方式的分析结果表明引入“关系网模型”可有效提高算法的收敛速度，并能在一定程度上提高解的质量．

一种基于扩展规则的撑SAT求解系统1714-1725

摘要：#SAT问题是SAT问题的扩展，需要计算出给定命题公式集合的模型个数，通过将问题求解沿着归结的反方向进行，并利用容斥原理解决由此带来的空间复杂性问题，提出了一种基于扩展规则的模型计数和加权模型计数问题求解框架，可以看作是目前所有模型计数问题求解方法的一种补方法．证明了该方法的完备性和有效性，设计了基于扩展规则的#SAT求解系统：JLU-ERWMC，实验结果表明，JLU-ERWMC在有些问题中优于目前最为高效的#SAT问题求解系统．

基于边界力的Mean—Shift核窗宽自适应算法1726-1734

摘要：针对Mean-Shift（中值漂移）算法中核函数带宽不能实时改变的缺陷，提出一种基于边界力的Mean-Shift核函数带宽自适应更新算法．在分析目标加权核直方图模型的基础上，引入区域似然度以提取目标的局部信息．然后，比较相邻帧间的区域似然度并构建边界力．通过对边界力的计算，得到边界点的位置，进而自适应地更新核函数带宽．实验结果表明，这些工作改善了Mean-Shift算法在目标尺度和形态发生变化时的跟踪效果，并且可以满足实时性的需要．

潜在属性空间树分类器1735-1745

摘要：提出一种潜在属性空间树分类器（latent attribute space tree classifier，简称LAST）框架，通过将原属性空间变换到更容易分离数据或更符合决策树分类特点的潜在属性空间，突破传统决策树算法的决策面局限，改善树分类器的泛化性能．在LAST框架下，提出了两种奇异值分解斜决策树（SVD（singular value decomposition）oblique decision tree，简称SODT）算法，通过对全局或局部数据进行奇异值分解，构建正交的潜在属性空间，然后在潜在属性空间内构建传统的单变量决策树或树节点，从而间接获得原空间内近似最优的斜决策树．SODT算法既能够处理整体数据与局部数据分布相同或不同的数据集，又可以充分利用有标签和无标签数据的结构信息，分类结果不受样本随机重排的影响，而且时间复杂度还与单变量决策树算法相同．在复杂数据集上的实验结果表明，与传统的单变量决策树算法和其他斜决策树算法相比，SODT算法的分类准确率更高，构建的决策树大小更稳定，整体分类性能更鲁棒，决策树构建时间与C4．5算法相近，而远小于其他斜决策树算法．

基于网络挖掘的上下文相关词汇级复述研究1746-1755

摘要：词汇级复述研究旨在为词汇获取复述．词汇级复述是上下文相关的，即对同一个词在不同上下丈中应获取不同的复述词．提出了一种获取上下文相关词汇级复述的方法．该方法包括两部分：基于网络挖掘的候选复述词获取以及基于二元分类的复述词确认．在《人民日报》语料库上的实验结果表明：（1）基于网络挖掘的候选复述词获取方法是切实可行的，平均为每个待复述词在每个给定的上下文句子中获取2．3个正确复述词：（2）利用二元分类的方法进行复述确认是有效的，其，值达到0．6023；（3）利用该方法抽取得到的复述中，有75．11％和98.31％无法通过两种常用的上下文无关方法，即基于辞典和基于聚类的方法来获得，这证明了所提出的上下文相关复述方法可以有效地补充传统的上下文无关方法．

基于相关分析的多数据流聚类1756-1767

摘要：提出基于相关分析的多数据流聚类算法．该算法将多数据流的原始数据快速压缩成一个统计概要．根据这些统计概要，可以增量式地计算相关系数来衡量数据间的相似度．提出了一种改进的k-平均算法来生成聚类结果．改进的缸平均算法可以动态、实时地调整聚类数目，并及时检测数据流的发展变化．还将算法应用到按照用户要求的聚类问题（COD），使得用户可以在任意的时间区间上查询聚类结果．提出了一种合理的时间片断划分机制，使得用户指定的任意时间区间都可以由这些时间片断组合而成．在模拟和真实数据上的实验结果都表明，该算法比其他方法具有更好的聚类质量、速度和稳定性，能够实时地反映数据流的变化．

软件学报杂志数据库技术

全文索引技术时空效率分析1768-1784

摘要：全文索引技术（gull-text index technique）作为提高全文检索时空效率的有效方式之一，近年来得到了广泛而深入的研究．根据全文索引实现技术的不同，将其分为三大类：索引技术、压缩与索引混合技术以及自索引技术（self-index technique）．从上述分类角度综述了全文索引时空效率方法中具有代表性的一些方法和技术：倒排文件、签名丈件、后缀树与后缀数组、基于这3种索引的压缩技术、基于倒排丈件的自索引与基于后缀教组的自索引的基本原理、所面临的问题及进展，并对这些技术的时空性能进行了详细的分析和比较。分析了各种技术的适应环境及优劣．最后总结了上述技术的特点，指出了存在的问题以及未来的研究方向．

2009中国计算机大会征文通知1784-1784

摘要：2009中国计算机大会将于2009年10月23日～24日在天津举行。中国计算机大会（China National Computer Conference,简称CNCC）是中国计算机学会2003年创建的系列性学术活动，

压缩数据库中一种自适应直方图的构建1785-1799

摘要：直方图在查询优化过程中起着重要作用．在压缩数据库中利用查询处理的特点构建自适应直方图以便于查询优化或近似回答查询是尚待解决的问题．通过对查询缓冲池内的查询进行调度来追踪热点数据，并用查询结果中的反馈信息构建自适应直方图以加快自适应直方图的收敛速度．另外，还提出一种参数化方法来估计未被任何桶覆盖的区域中元组的个数．该直方图可以增量式地被维护．实验结果表明，这种直方图具有良好的平均精度、更快的收敛速度和更强的自适应能力．

P2P网络中时变数据的近似聚集方法1800-1811

摘要：随着P2P技术在电子商务等领域的广泛应用，对分布在P2P网络中的数据进行聚集操作的需求越来越迫切．但是，由于P2P网络的大规模及分散性，这种聚集操作的实现颇具挑战性．而且在很多应用中，P2P网络中的数据往往是随时间变化的，这进一步增加了聚集操作的难度．现有P2P网络中的聚集算法均假定网络中的数据是非时变的。如果将其直接应用在存在时变数据的P2P网络中，则会因为其聚集时间过长而导致聚集过程中数据已经发生变化的问题．为此，提出了一种P2P网络中基于均衡采样的时变数据近似聚集算法，理论分析和实验结果表明，该聚集算法在处理时变数据时优于已有的算法，可以有效地应用于存在时变数据的P2P网络中．

一种支持高效XML路径查询的自适应结构索引1812-1824

摘要：提出了一种新的自适应结构索引：AS-Index（adaptive structural index），能够克服现有静态索引和自适应索引的缺陷，具备高效的查询和调整性能．AS-Index建立在F＆B—Index的基础之上，其索引结构包括F＆B-Index,Query-Table和Part-Table．Query—Table能够记录频繁查询，避免了查询过程中的冗余操作．并且，在Query-Table的基础上提出了自底向上的查询处理过程，能够充分利用现有的频繁查询高效地回答非频繁查询．Part-Table用于优化包含祖先后裔边的查询，进一步提高了查询性能．现有的自适应结构索引的调整粒度是XML元素节点，调整过程往往需要遍历整个文档．而AS-Index是基于F＆B-Index节点的增量调整，其过程是局部的，高效的，并且能够支持复杂分支查询的调整．实验结果表明，AS-Index在查询和调整性能上优于现有的XML结构索引．同时，相比于现有的自适应结构索引，AS-Index针对大规模文档具有更加优良的可扩展性．

有效预处理P2P网络中的子空间skyline查询1825-1838

摘要：多维空间的skyline查询处理是近年来数据库领域的一个研究重点和热点．Vlachou等人首次考虑如何在P2P网络中有效进行子空间上的skyline查询，并提出“扩展skyline集合”的概念来减少预处理时的网络传输量．然而实验评估表明，扩展skyline集合只能有限地减少予空间skyline查询预处理的教据传输量．基于此，提出一种缩减预处理时数据传输量的有效方法TPAOSS（three—phase algorithm for optimizing skyline scalar）．TPAOSS算法根据全空间skyline集合与子空间skyline集合间的语义关系分3个阶段来传输必要的数据，其中第l阶段发送全空间skyline对象；第2阶段接收种子skyline对象；而第3阶段基于Bloom filter技术发送种子skyline对象在子空间上的重复对象．为了降低第2阶段的数据传输量，给出两种接收种子skyline对象的有效策略．理论分析和实验评估结果表明，所给出的算法具有有效性和实用性．

基于矩阵加权关联规则挖掘的伪相关反馈查询扩展1854-1865

摘要：提出一种面向查询扩展的矩阵加权关联规则挖掘算法，给出与其相关的定理及其证明过程．该算法采用4种剪枝策略，挖掘效率得到极大提高．实验结果表明，其挖掘时间比原来的平均时间减少87．84％．针对现有查询扩展的缺陷，将矩阵加权关联规则挖掘技术应用于查询扩展，提出新的查询扩展模型和更合理的扩展词权重计算方法．在此基础上提出一种伪相关反馈查询扩展算法——基于矩阵加权关联规则挖掘的伪相关反馈查询扩展算法，该算法能够自动地从前列n篇初检文档中挖掘与原查询相关的矩阵加权关联规则，构建规则库，从中提取与原查询相关的扩展词，实现查询扩展．实验结果表明，该算法的检索性能确实得到了很好的改善．与现有查询扩展算法相比，在相同的查全率水平级下，其平均查准率有了明显的提高．

移动对象数据库模型、查询语言及实时交通流分析1866-1884

摘要：提出一种移动对象数据库模型——Dvnamic Transportation Network Based Moving Objects Database（简称DTNMOD），并给出了DTNMOD中基于移动对象时空轨迹的网络实时动态交通流分析方法．在DTNMOD中，交通网络被表示成动态的时空网络，可以描述交通状态、拓扑结构以及交通参数随时间的变化过程：网络受限的移动对象则用网络移动点表示．DTNMOD模型包含了完整的数据类型和查询操作的定义，因此可以在任何可扩充数据库（如PostgreSQL或SECONDO）中实现，从而得到完整的数据库模型和查询语言．为了对相关模型的性能进行比较与分析，基于PostgreSQL实现了一个原型系统并进行了一系列的实验．实验结果表明，DTNMOD提供了良好的区域查询及连接查询性能．

软件学报杂志计算机网络与信息安全

传感器网络中健壮数据聚集算法1885-1894

摘要：节约能量以提高网络寿命是传感器网络研究面临的重要挑战网内聚集查询在中间节点对数据进行预处理，可以减少消息传送的数量或者大小，从而实现能量的有效利用，但是，目前的聚集查询研究假设采样数据都是正确的．而目前的异常检测算法以检测率作为首要目标，不考虑能量的消耗，也不考虑查询的特点．所以将两方面的研究成果简单地结合在一起并不能产生很好的效果．分析了错误和异常数据可能对聚集结果造成的影响，提出了健壮聚集算法RAA（robust aggregation algorithm）．RAA对传统聚集查询进行了改进，在聚集的同时利用读向量相似性判断数据是否发生了错误或异常，删除错误数据，聚集正常数据并报告异常，使用户可以对网络目前状况有清晰的理解．最后，比较了RAA和TAG Voting（在使用TAG（tiny aggregation）算法聚集的同时利用Voting算法进行异常检测），实验结果表明，RAA算法在能量消耗和异常检测率方面都优于TAG Voting．

面向多跳无线网络的无冲突MAC协议1895-1908

摘要：多跳无线网络中隐藏节点导致节点之间的冲突频繁、数据重传率高、网络吞吐量下降．而802．11 DCF中的RTS／CTS（ready-to-send／clear-to-send）机制不能有效地防止隐藏节点，特别是随着网络中节点通信速率的提高，由于节点的信噪比要求也相应提高，接收节点受到更大范围内隐藏节点的干涉，RTS／CTS机制防止隐藏节点的效率急剧降低．首先，在考虑网络积累干涉以及环境噪音的情况下分析了多跳无线网络中的隐藏节点问题．然后，提出一种双信道无冲突MAC（media access control）协议DCCFMA（double channel collision flee media access）．DCCFMA协议采用双信道结构，接收节点根据数据信道中发送节点的信号强度动态调节控制信道的发射功率，以完全覆盖接收节点周围所有的隐藏节点，保证接收节点在接收过程中不受干涉．DCCFMA协议能够有效地解决多跳无线网络中的隐藏节点问题．仿真结果表明，与802．11DCF相比，DCCFMA机制下的平均网络吞吐量增加了24％．

一种对等网中基于相互信任的两层信任模型1909-1920

摘要：在P2P系统中，声誉模型是建立节点间信任关系的重要方法之一，但现有的P2P声誉模型几乎都是纯分散式的，具有信任收敛慢、信任管理复杂和网络开销大等缺点．在TLT（two-level trust）中，节点自发组织为信任簇，信任评价以簇为单位．每个簇由簇首和成员节点组成，簇首和成员节点之间是一种相互信任的关系：簇首为了提高自身的簇间服务信任，利用簇内服务信任观察成员节点的服务性能，过滤恶意的成员节点；成员节点为了提高服务声誉和接受更好的服务，利用信任考察簇首的管理能力．分析和仿真结果表明：在TLT中，节点的信任值收敛快，恶意行为能够被快速识别；TLT可扩展性好，如信任管理简单和网络开销小．

保障连续媒体流用户层QoS的缓存控制1921-1930

摘要：研究了缓存控制对媒体流用户层QoS的影响．多媒体系统信宿端通常采用播放缓存来补偿时延抖动．提高媒体流播放的连续性．缓存控制虽然能够降低时延抖动的影响，却增加了端到端时延．时延或时延抖动是用户可感知的QoS参数，缓存控制对用户层QoS的影响究竟如何呢？利用已有的应用层向用户层QoS映射的研究结果，分析缓存控制参数与端到端QoS参数、应用层QoS参数的关系，获得了缓存控制参数与用户层QoS参数的关系．从理论上深入挖掘缓存控制对用户层QoS参数的作用，给出了提供确定时延和时延抖动保障的缓存容量值，论证了在网络环境一定时存在提供最佳用户层QoS的缓存容量值．实验结果验证了分析．