Global data computation in chordal rings

Existing Global Data Computation (GDC) protocols for asynchronous systems are round-based algorithms designed for fully connected networks. In this paper, we discuss GDC in asynchronous chordal rings, a non-fully connected network. The virtual links approach to solve the consensus problem may be applied to GDC for non-fully connected networks, but it incurs high message overhead. To reduce the overhead, we propose a new non-round-based GDC protocol for asynchronous chordal rings with perfect failure detectors. The main advantage of the protocol is that there is no notion of rounds. Every process creates two messages initially, with one message traversing in a clockwise direction and visiting each and every process in the chordal ring. The second message traverses in a counterclockwise direction. When there is direct connection between two processes, a message is sent directly. Otherwise, the message is sent via virtual links. When the two messages return, the process decides according to the information maintained by the two messages. The perfect failure detector of a process need only detect the crash of neighboring processes, and the crash information is disseminated to all other processes. Analysis and comparison with two virtual links approaches show that our protocol reduces message complexity significantly.     

Range mode and range median queries in constant time and sub-quadratic space

Given a list of n items and a function defined over sub-lists, we study the space required for computing the function for arbitrary sub-lists in constant time.For the function mode we improve the previously known space bound O(n²/logn) to O(n²loglogn/log²n) words.For median the space bound is improved to O(n²loglog²n/log²n) words from O(n²⋅log(k)n/logn), where k is an arbitrary constant and log(k) is the iterated logarithm.     

A genetic algorithm with gene rearrangement for K-means clustering

In this paper, a new clustering algorithm based on genetic algorithm (GA) with gene rearrangement (GAGR) is proposed, which in application may effectively remove the degeneracy for the purpose of a more efficient search. A new crossover operator that exploits a measure of similarity between chromosomes in a population is also presented. Adaptive probabilities of crossover and mutation are employed to prevent the convergence of the GAGR to a local optimum. Using the real-world data sets, we compare the performance of our GAGR clustering algorithm with K-means algorithm and other GA methods. An application of the GAGR clustering algorithm in unsupervised classification of multispectral remote sensing images is also provided. Experiment results demonstrate that the GAGR clustering algorithm has high performance, effectiveness and flexibility.     

An enhanced Web page change detection approach based on limiting similarity computations to elements of same type

This paper describes an efficient Web page detection approach based on restricting the similarity computations between two versions of a given Web page to the nodes with the same HTML tag type. Before performing the similarity computations, the HTML Web page is transformed into an XML-like structure in which a node corresponds to an open-closed HTML tag. Analytical expressions and supporting experimental results are used to quantify the improvements that are made when comparing the proposed approach to the traditional one, which computes the similarities across all nodes of both pages. It is shown that the improvements are highly dependent on the diversity of tags in the page. That is, the more diverse the page is (i.e., contains mixed content of text, images, links, etc.), the greater the improvements are, while the more uniform it is, the lesser they are.     

具有计算可靠性的符号模型

MW方法仅考虑使用公钥加密原语,不包含{{mk}k类型消息的双方协议。针对该问题,使用公钥加密和对称加密,建立扩展标记符号模型与扩展计算模型,论证扩展标记符号模型的计算可靠性,实现对MW方法的扩展。     

考虑用户活跃度和项目流行度的基于项目最近邻的协同过滤算法

项目相关性度量是基于项目最近邻的协同过滤算法的关键。已有的项目相关性度量方法在数据集稀疏或推荐低流行度产品时会面临较大挑战,因此提出一种考虑用户活跃度和项目流行度的基于项目最近邻的协同过滤算法。该算法在度量两个项目的相关性时,若有记录只对两个项目之一有评分,则利用该记录所对应的评分用户的活跃度和被评价项目的流行度进行相关性惩罚,从而提高数据稀疏环境下低流行度产品被推荐的概率。实验表明,所提算法在保证评分预测精度的情况下提升了推荐结果的多样性和新颖性。     

一种基于领域本体的稿件—审阅人相关度度量方法

随着稿件数量的不断增长,审阅人指派越来越成为会议组织者、期刊编辑和基金委员会的一项费时费力的工作,计算机辅助审阅人指派研究也由此得到了更多的关注。稿件—审阅人相关度度量是该研究中的一个重点问题。该文设计了一种基于领域本体的稿件—审阅人相关度度量方法。该方法由文档关键词提取、领域本体的自动构建及基于网络流模型的稿件—审阅人相关度计算等部分组成。初步实验表明,该方法在国家自然科学基金申请书申请代码分配的任务中取得较好表现,优于单纯基于关键词字串相似度的方法。     

基于3种群Lotka-Volterra模型的种群动力学函数优化算法

基于3种群Lotka-Volterra模型构造出了可全局收敛的种群动力学优化算法。在该算法中,每个种群对应着优化问题的一个试探解;基于3种群间的每种相互作用关系,提出了相应的图形表示方法以及对应的Lotka-Volterra模型构建方法,种群间的相互作用关系包括竞争关系、互惠共存关系、捕食-被食关系或者它们间的任意组合;3种群间的每种相互作用关系均对应着一种种群进化算子,该算子的数学表达式就是其对应的Lotka-Volterra模型的离散化表达式;另外,为了求解更复杂的优化问题求解,将种群融合、突变和选择等行为也构造成操作算子。所有算子的特性可以确保整个种群的适应度指数要么保持原状不变,要么向好的方向转移,从而确保了算法的全局收敛性;在种群演变过程中,种群从一种状态转移到另一种状态实现了种群对优化问题最优解的搜索。应用可归约随机矩阵的稳定性条件证明了本算法具有全局收敛性。测试结果表明本算法是高效的。