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

软件学报 2007年第02期杂志 文档列表

软件学报杂志算法设计与分析

基于小波和偶合特征的多数据流压缩算法177-184

摘要：提出了基于Haar小波技术和偶合特征的多数据流压缩方法．主要研究成果包括：（1）证明了Haar小波变换服从能量守恒规律，并用于压缩数据流；（2）揭示了数据流的偶合度与变化趋势的相关性、偶合度的平移不变性及等价规律，采用特征流序列的小波系数和流能量近似表示流的趋势，达到压缩的目的；（3）提出了多尺度能量分解模型，提高了表示精度；（4）设计了多尺度能量分解压缩算法以及多尺度重构算法：（5）在真实数据集上的实验表明，新方法的压缩比是传统小波方法的2-4倍．

基于最大权值路径算法的DNA多序列比对方法185-195

摘要：针对生物序列分析中的多序列比对问题，当输入数据量比较大时，人们提出了很多启发式的算法来改善计算速度和比对结果．提出了用于进行全局DNA多序列比对的一种方：MWPAlign（maximum weighted pathalignment）．该算法把序列信息用de Bruijn图的形式表示，并将输入序列的信息记录在图的边上，这样，就将求调和序列的问题转化为求图的最大权值路径问题，使多序列比对问题的时间复杂度降低到几乎线性．实验结果显示：MWPAlign是可行的多序列比对算法，尤其对于变异率低于5．2％的大量序列数据，相对于CLUSTALW（cluster alignments weight），T-Coffee和HMMT（hidden Markov model training）有较好的比对结果和运算性能．

2007年粗糙集与软计算、Web智能、粒计算联合学术会议征文通知195-195

语言建模中最小化样本风险算法的研究和改进196-204

摘要：目前，一些主流的判别学习算法只能优化光滑可导的损失函数，但在自然语言处理（natural language processing，简称NLP）中，很多应用的直接评价标准（如字符转换错误数（character error rate，简称CER））都是不可导的阶梯形函数．为解决此问题，研究了一种新提出的判别学习算法——最小化样本风险（minimum samplerisk，简称MSR）算法．与其他判别训练算法不同，MSR算法直接使用阶梯形函数作为其损失函数．首先，对MSR算法的时空复杂性作了分析和提高；同时，提出了改进的算法MSR—Ⅱ。使得特征之间相关性的计算更加稳定．此外，还通过大量领域适应性建模实验来考察MSR-Ⅱ的鲁棒性．日文汉字输入实验的评测结果表明：（1）MSR／MSR—Ⅱ显著优于传统三元模型，使错误率下降了20．9％；（2）MSR／MSR—Ⅱ与另两类主流判别学习算法Boosting和Pereeptron现相当；（3）MSR-Ⅱ不仅在时空复杂度上优于MSR，特征选择的稳定性也更高；（4）领域适应性建模的结果证明了MSR—Ⅱ的良好鲁棒性．总之，MSR／MSR—Ⅱ是一种非常有效的算法．由于其使用的是阶梯形的损失函数，因此可以广泛应用于自然语言处理的各个领域，如拼写校正和机器翻译．

Mean Shift算法的收敛性分析205-212

摘要：作为迭代算法，MeanShift的收敛性研究是应用的基础，而Comaniciu和李乡儒分别证明了MeanShift的收敛性，但证明过程存在错误．首先指出了Comaniciu和李乡儒的证明过程存在错误；然后，从数学上重新证明了MeanShift算法的局部收敛性，并指出其收敛到局部极大值的条件；最后，从几何上举反例分析了MeanShift的收敛性，并进行了深入比较和讨论．这为MeanShift算法的深入研究及应用奠定了基础．

图同构中的一类顶点细分方法213-219

摘要：提出一种顶点细分方法．基于顶点之间具有一定长度的路径数等信息，定义了一类顶点不变函数．将该方法与已有的一些顶点细分方法进行了比较．分析表明，基于路径数的顶点不变函数的细分效果，至少不差于基于顶点的度、距离等方法；而一些实例则表明前者要优于后者．基于路径数的顶点分类方法可以有效地用于图同构算法，能够降低所需比较的顶点数，达到快速搜索的效果．

系统级综合中结合资源分配的调度算法220-228

摘要：在系统级综合中，资源的分配通常由设计者指定，或在设计空间搜索的最外层循环中进行枚举探索．提出了一种结合资源分配的启发式调度算法沱根据当前系统划分的结果，在调度过程中寻找合适的所需资源实例的数目，从而确定系统的资源分配以及调度指派方案．应用该调度算法可使设计空间搜索过程简化为划分、调度和评估三个步骤，省去了最外层的资源分配枚举循环，提高了搜索效率．实验结果验证了该算法的可行性和有效性.

全国电子政务技术及应用学术研讨会（EGTA2007）征文通知228-228

摘要：<正>为促进我国电子政务建设,推动国内电子政务相关技术和应用研究成果的交流,中国计算机学会暨电子政务与办公自动化专委会决定于2007年9月14日~16日在中国人民大学召开全国电子政务技术与应用学术研讨会。会议将就电子政务建设相关的关键共性技术、项目方案设计、实施与应用等问题进行深层次的研讨。论文集将由《武汉大学学报(英文)》(EI源刊)、核心期刊《计算机科学》专刊和中央级出版社出版。会议期间除了进行会议论文交流以外,还将邀请著名学者作特邀报告。欢迎从事电子政务技术与应用相关研究工作的专家、学者和企业界人士踊跃投稿。

带输入队列并行交换的负载平衡分析229-235

摘要：并行交换是新兴的交换技术，基于该技术能够利用小型交换模块来构建大容量的交换系统，例如太比特或更高容量的交换机．把带输入队列的并行交换称为带缓存并行交换（buffered parallel switch，简称BPS），重点研究其中并行且独立工作的交换模块之间的负载平衡问题．从不同角度出发，提出两种负载平衡的定义．基于两种定义，分别分析了BPS负载平衡的条件并提出分布式调度算法族．最后，提出一种简单而有效的调度算法，该算法能在无加速比BPS中同时满足两种定义，仿真实验结果表明了该算法的有效性和良好性能，另外，就算法的工程实现进行了讨论．

软件学报杂志数据库技术

基于目录路径的元数据管理方法236-245

摘要：提出目录路径属性与目录对象分离的元数据管理方法，扩展了现有的对象存储结构．该方法能够有效避免因为目录属性修改而导致的大量元数据更新与迁移；通过减少前缀目录的重迭缓存提高了元数据服务器Cache的利用率和命中率；通过减少遍历目录路径的开销和充分开发目录的存储局部性，减少了磁盘I／O次数；通过元数据服务器的动态负载均衡避免单个服务器过载．实验结果表明，该方法在提高系统性能、均衡元数据分布以及减少元数据迁夥等方面具有明显的优势．

全国第2届语义Web与本体论学术研讨会（SWON2007）征文通知245-245

摘要：<正>全国语义Web与本体论学术研讨会(SWON)是中国计算机学会暨电子政务与办公自动化专委会主办的系列会议SWON 2007会议将于2007年9月14日~16日在中国人民大学召开会议目的是为语义Web学术界和工业界提供一个交流平台,反映国际国内关于语义Web的最新研究成果和进展会议录用论文将由《东南大学学报》(英文版)(EI源刊)正刊专辑出版会议期间除了进行会议论文交流以外,还将邀请著名学者作特邀报告本次会议仍将评选大会优秀学生论文

时态数据挖掘的相似性发现技术246-258

摘要：现实世界存在着大量的时态数据，时态数据挖掘（tempoml data mining，简称TDM）是近年来学术界关注的一个重要研究课题相似性发现技术关注数据的发展变化，试图从时态数据中发现事物动态演化的相似性规律．分析和比较了近年来TDM研究中涉及的主要相似性发现技术．首先区分定义了3类时态数据：时间序列、事件序列和交易序列；然后分类并讨论了各种与序列相关的主要方法和技术，涉及相似性度量、序列抽象表示和搜索，以及各类挖掘任务及其算法操作；最后展望进一步研究的方向．

Peer数据管理系统中的视图维护策略259-267

摘要：研究Peer数据管理系统（peer data managementsystem，简称PDMS）中的视图维护策略．首先提出一种混合的P2P架构，在该架构中，Peer优先选择基本的P2P架构而不是超级Peer架构．如果一个视图沿着PDMS的一条语义链路传播，那么它通过重构能够从许多数据源检索到数据，因此扩展了视图的定义，提出peer视图、局部视图和全局视图；并且从一条语义链路的任意节点出发，同一查询都能够得到相同的结果．在PDMS中违接操作限制在各个局部PDMS中，这样，全局物化视图的维护就转化为对各相关局部物化视图的维护．在PDMS中。一个视图可能涉及到多个表的连接，根据该应用的需要扩展了Mork的规则系统．根据扩展了的规则系统进行更新数据传播。同时依据该规则系统提出一种算法来维护PDMS中的视图．最后进行实验验证．实验结果表明，该视图维护策略比Mork的视图维护策略的性能要好．

可伸缩的增量连续k近邻查询处理268-278

摘要：针对基于TPR树（time—parameterized R-tree）索引的大量并发CKNN（continuousk-nearestneighbor）查询处理提出了一种可伸缩的增量连续k近邻查询处理（scalable processing of incremental continuous k-nearest neighbor queries，简称SI-CNN）框架，通过引入搜索区域进行预裁剪以减少查询更新所需要的TPR树节点访问代价，并引入了增量结果表以保存候选对象，批量地更新查询结果集，具有良好的可伸缩性．基于SI—CNN框架提出了一种增量更新的SI-CNN查询处理算法，能够基于上次查询结果增量的更新查询，支持查询集合中加入或删除查询和移动对象数据集的插入、删除等动态更新操作．实验结果与分析表明，基于SI—CNN框架的SI—CNN算法可以很好地支持大量并发的CKNN查询处理，具有起好的实用价值．

一种基于概率模型的预测性时空区域查询处理279-290

摘要：提出了一种基于概率模型的预测性时空区域查询处理方法．该方法采用Filter—Refinement方式采处理查询．首先，从数据库中选择所有可能满足查询的候选移动对象；然后，根据概率模型中定义的方法采计算候选移动对象满足查询的概率；最后，根据查询中指定的最小概率阈值过滤候选移动对象并返回查询结果．该概率模型将移动对象未来可能出现的位置定义为一个随机变量，并给出了计算移动对象在两种不同的运动模式下满足查询的概率值的方法．还提出了一种通过对大量历史轨迹抽样来获得概率密度函数（pmbability density function，简称PDF）的轨迹分析算法，并设计了概率密度函数索引STP-Index（spatio-temporal PDF-index）．该索引能够有效地提高轨迹分析算法和概率计算的效率，实验结果表明，该查询处理方法能够有效地支持预测性时空区域查询的处理，提高查询结果的正确性，特别适合于具有较小的空间区域和长时间范围的预测性时空区域查询．

基于图形处理器的数据流快速聚类291-302

摘要：在数据流环境下，聚类算法不仅需要有较高的聚类质量，同时需要有实时处理速度．因而，提出了一类基于图形处理器（graphics processing unit，简称GPU）的快速聚类方法，包括基于K-means的基本聚类方法、基于GPU的数据流聚类以及数据流簇进化分析方法．这些方法的共同特点是充分利用了GPU强大的处理能力和流水线特性．与以往具有独立框架的数据流聚类算法不同，这些基于GPU的聚类算法具有同一框架和多种聚类分析功能，为数据流聚粪分析提供了统一的平台．从分析可知，数据流聚类分析的核心操作实际上就是距离计算和比较．基于这一认识，利用GPU的子素向量处理功能进行距离计算．性能验证实验是在配有Pentium IV 3．4GCPU和NVIDIA GeForce 6800GT显卡的Pc上进行的．综合分析和实验结果表明，基于GPU的数据流聚类算法比传统的CPU算法平均快7倍，从而为高速数据流应用提供了良好的支持．

Web仓储中视图变化频率的自适应估测303-310

摘要：物化视图的刷新是Web仓储进行系统维护的一项主要任务，而基础数据变化频率则是刷新方案中的重要因素．在已有文献中，研究者已经给出一些关于基础数据变化规律的算法和估测器．虽然这些估测器取得了不错的效果，然而他们却忽略了这些估测器都有一定的适用范围，超出这个范围则效果急剧下降．在此，基于泊松过程进行分析，对估测器的适用范围进行了讨论。根据估测结果的偏离值和有效性对估测公式进行参数调整，同时根据估测值的大小不断调整数据源的访问频率和次数，从而使数据源访问模式和估测器互相适应，使估测器在最佳估测范围内获得估测值．实验结果表明，与已有文献中的方法相比，新提出的自适应估测算法能够取得更好的效果．

一种基于概念相似度的数据分类方法311-322

摘要：依据数据属性间的相似信息，提出了一种分类方法．该方法将属性矢量化，属性作为m维空间的基本矢量。数据记录作为属性矢量的和彳4用属性间先验的概念相似信息，给出了求取任意属性矢量对的相似距离算法，并将数据间相关度计算转换为属性矢量及其相互投影的公式，从而得到任意两条数据的相关度；利用相关度，提出了一种分类算法．用详实的实验证明了该算法的有效性．