A Functional Approach to External Graph Algorithms

We present a new approach for designing external graph algorithms and use it to design simple, deterministic and randomized external algorithms for computing connected components, minimum spanning forests, bottleneck minimum spanning forests, maximal independent sets (randomized only), and maximal matchings in undirected graphs. Our I/ O bounds compete with those of previous approaches. We also introduce a semi-external model, in which the vertex set but not the edge set of a graph fits in main memory. In this model we give an improved connected components algorithm, using new results for external grouping and sorting with duplicates. Unlike previous approaches, ours is purely functional—without side effects—and is thus amenable to standard checkpointing and programming language optimization techniques. This is an important practical consideration for applications that may take hours to run.     

A Functional Approach to External Graph Algorithms

Abstract. We present a new approach for designing external graph algorithms and use it to design simple, deterministic and randomized external algorithms for computing connected components, minimum spanning forests, bottleneck minimum spanning forests, maximal independent sets (randomized only), and maximal matchings in undirected graphs. Our I/ O bounds compete with those of previous approaches. We also introduce a semi-external model, in which the vertex set but not the edge set of a graph fits in main memory. In this model we give an improved connected components algorithm, using new results for external grouping and sorting with duplicates. Unlike previous approaches, ours is purely functional—without side effects—and is thus amenable to standard checkpointing and programming language optimization techniques. This is an important practical consideration for applications that may take hours to run.     

一种新的属性图重叠聚类挖掘算法

属性图各节点附有的节点属性标签,为节点提供了更加丰富的信息,在数据挖掘应用,特别是数据聚类问题中如何有效利用这些丰富的信息,已经成为开展此类研究的研究目的.不同于传统图聚类,属性图上的聚类要同时考虑图的结构信息和节点的属性信息,因此如何平衡两者之间的关系,这是属性图聚类主要关注所在.目前已提出的属性图聚类算法,部分算法的效率很高,然而聚类质量较差,同时一些算法可以得到较好的聚类结构,然而算法消耗大量的系统资源,效率也较低.这些算法均没有考虑簇之间存在重叠的情况,这导致无法得到更高精度的聚类结构.因而提出一种属性图上的重叠聚类挖掘算法,实验表明,提出的算法可以得到更高的聚类精度,特别是可以提升聚类内部节点的属性相似度.     

EFSM最小可达图的同步生成算法

针对EFSM可达性分析过程中的状态空间爆炸问题,提出了一种基于变量值域划分的EFSM最小可达图的同步生成算法。该算法将EFSM可达图的生成与最小化两个过程结合在一起同步进行,引入特征配置的思想,依据特征配置指出变迁有效性组合,以及变迁的赋值动作与终止状态分组变量值域的关系,在进行可达性分析的同时仅对可达的状态分组进行稳定性判定及必要的分裂,直到所有可达状态分组均稳定为止,EFSM最小可达图即构造完毕。文中算法最大限度地减小了中间结果如不可达分组等对求解过程的影响,从而降低了传统算法因可达性分析与最小化过程相分离而引起的时间与空间上的巨大代价。     

A Synchronization Approach for the Minimization of Contouring Errors of CNC Machine Tools

This paper presents a synchronization control approach for the minimization of contouring errors of multi-axis CNC machine tools. The contouring errors are presented by the position synchronization errors that are defined as differential position errors between each axis and its adjacent ones. Using cross-coupling concept, a decentralized tracking controller is developed with feedback of both position and synchronization errors, formed with a combination of feedforward, feedback and a saturation control. It is proven that this controller can asymptotically stabilize both position and synchronization errors to zero. The proposed controller does not require significant use of the system dynamic models. Experiments performed on a multi-axis machine tool demonstrate improved performance especially in the contouring error minimization.     

A Graph Approach to Quantitative Analysis of Control-Flow Obfuscating Transformations

Modern obfuscation techniques are intended to discourage reverse engineering and malicious tampering of software programs. We study control-flow obfuscation, which works by modifying the control flow of the program to be obfuscated, and observe that it is difficult to evaluate the robustness of these obfuscation techniques. In this paper, we present a framework for quantitative analysis of control-flow obfuscating transformations. Our framework is based upon the control-flow graph of the program, and we show that many existing control-flow obfuscation techniques can be expressed as a sequence of basic transformations on these graphs. We also propose a new measure of the difficulty of reversing these obfuscated programs, and we show that our framework can be used to easily evaluate the space penalty due to the transformations.      

A Variational Loop Shrinking Analogy for Handle and Tunnel Detection and Reeb Graph Construction on Surfaces

The humble loop shrinking property played a central role in the inception of modern topology but it has been eclipsed by more abstract algebraic formalisms. This is particularly true in the context of detecting relevant non-contractible loops on surfaces where elaborate homological and/or graph theoretical constructs are favored in algorithmic solutions. In this work, we devise a variational analogy to the loop shrinking property and show that it yields a simple, intuitive, yet powerful solution allowing a streamlined treatment of the problem of handle and tunnel loop detection. Our formalization tracks the evolution of a diffusion front randomly initiated on a single location on the surface. Capitalizing on a diffuse interface representation combined with a set of rules for concurrent front interactions, we develop a dynamic data structure for tracking the evolution on the surface encoded as a sparse matrix which serves for performing both diffusion numerics and loop detection and acts as the workhorse of our fully parallel implementation. The substantiated results suggest our approach outperforms state of the art and robustly copes with highly detailed geometric models. As a byproduct, our approach can be used to construct Reeb graphs by diffusion thus avoiding commonly encountered issues when using Morse functions.     

Graph Approach to Solving Problems of Combinatorial Recognition

The problem of finding two radioactive balls among a given set of balls is reduced to a combinatorial recognition problem, and the latter is solved by a series of tests. Methods of graph theory are used to solve the problem. The approach is illustrated by an example with 22 balls.     

一种基于模式的汉语句予相似度计算方法

句子相似度计算是EBMT系统实现的关键.本文将模式这一特殊的句子结构形式应用于汉语句子相似度计算,并给出了基本的实现算法.     

An Ontology-Based Approach to Metaphor Cognitive Computation

Language understanding is one of the most important characteristics for human beings. As a pervasive phenomenon in natural language, metaphor is not only an essential thinking approach, but also an ingredient in human conceptual system. Many of our ways of thinking and experiences are virtually represented metaphorically. With the development of the cognitive research on metaphor, it is urgent to formulate a computational model for metaphor understanding based on the cognitive mechanism, especially with the view to promoting natural language understanding. Many works have been done in pragmatics and cognitive linguistics, especially the discussions on metaphor understanding process in pragmatics and metaphor mapping representation in cognitive linguistics. In this paper, a theoretical framework for metaphor understanding based on the embodied mechanism of concept inquiry is proposed. Based on this framework, ontology is introduced as the knowledge representation method in metaphor understanding, and metaphor mapping is formulated as ontology mapping. In line with the conceptual blending theory, a revised conceptual blending framework is presented by adding a lexical ontology and context as the fifth mental space, and a metaphor mapping algorithm is proposed.     

图的最小顶点覆盖问题的面上DNA解法

1994年，Adleman提出一种解决NP完全问题的新方法-DNA计算．之后又出现了许多关于DNA计算的改进操作并增加了其可靠性，其中面上操作是一种很有效的方法．本文利用DNA计算的固态处理(面上计算)解决了图论中又-NP完全问题一图的最小顶点覆盖问题．构造了含有6个顶点10条边的图的顶点集子集对应的数据池之后，进行了一系列的合成、杂交、清洗、变性等生物操作，得到所有覆盖对应的DNA序列，然后通过编址过程得到所要求的最小覆盖．     

Graph Theoretic Approach to Steganography to Secure Message Digest

ABSTRACT

Recent attacks presented for Secure Hash Algorithm -1 (SHA -1) and Message Digest 5 (MD5) have drawn attention of researchers and information security managers to look for a way to secure it. Visibility of information, whether encrypted or not, provides worst kind of vulnerability. Possibility of finding collisions by attackers can be made practically infeasible if statistics related to message digest is denied by hiding the digest. Complicating the process of digest creation may solve the problem temporarily. However it can not discourage the hackers from doing so. If the created digest is hidden in some cover object, it makes difficult for hackers to collect statistics that helps in finding possible collisions. In this paper, we introduce a graph theoretic approach to steganography to hide digest into extra bytes of a Bit Map Pixel (BMP) file. This approach can also be used for securing any fixed length keys during key exchange in Public Key Infrastructure (PKI).     

Robust Computation of Intersection Graph between Two Solids

We propose a new robust algorithm for Boolean operations on solid models. The algorithm produces a consistent intersection graph between two input solids whose geometrical data are represented in floating point numbers. In order to prevent numerical calculation errors and inaccuracy of input data from causing inconsistency of the output, we put higher priority on symbolical connectivity of the edge-face intersection points than their numerical nearness. Each edge-face intersection point is symbolically represented using face names, which generate connectivity relations between the intersection points and the intersection line segments. The symbols with the same connectivity are made into clusters. The intersection line segments connected together at their end clusters form the intersection graph of two solids. Inconsistency of the connectivity of the clusters is detected and the intersection graph is corrected automatically. We describe the algorithm in detail for polyhedral solids, discuss extension to curves solids, and show its effectiveness by some examples of Boolean operations for two solids whose faces intersect at a very small angle.     

一种基于消解的变量极小不可满足子公式的提取方法

变量极小不可满足(VMU)问题是极小不可满足(MU)问题的一个扩充和延伸.着重研究VMU子公式的提取算法.首先从理论上比较MU和VMU的基本性质,并分析了目前流行的MU子公式提取算法.研究Davis-Putman-消解的基本性质,给出一个判定变量极小不可满足公式的充分必要条件,进而提出一个基于消解的VMU子公式提取算法.此算法可以使用ZBDDs压缩存储消解式,并实现单步多重消解.     

EDG—DCR：一种基于扩展有向图Web服务组合关系描述方法

Web服务组合是充分利用已有的Web服务,生成满足不同用户实际需要的组合服务的重要技术,Web服务组合关系的描述是Web服务组合的基础。目前,Web服务组合关系描述主要有两类方法,一是基于有向图的描述方法,二是基于Petri网、语义的描述方法。前一种方法简单,但不能描述所有的组合关系;后一种方法虽然能描述所有的组合关系,但是它们的组成元素过于复杂,用户难以理解和使用。文章以工作流模式为基础,提出一种基于扩展有向图的Web服务组合关系描述方法,使得其可以描述所有的组合关系。该描述方法使用XML Schema表示组合关系,保证描述过程的简单性、开放性和可扩展性。     

有向图并行计算中的多目标剖分算法

在以离散网格为基础的某些数值模拟中,网格间的数据依赖关系可以抽象为有向图．如何剖分这些有向图成多个子图,将各子图对应的数值模拟任务映射到不同的处理机,是该类数值模拟并行计算的基础．剖分算法中,需要综合考虑连通性、并行度、负载平衡、通信开销四个目标．文章在传统有向图剖分算法的基础上,提出了一个权衡这四个目标的有向图多目标剖分区域分解算法．应用于二维非结构网格上的柱对称中子输运并行计算中,通量扫描并行算法在该区域剖分算法上获得的并行效率比原来的无向图区域剖分算法高50％以上．     

Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation

This work presents a new perspective on characterizing the similarity between elements of a database or, more generally, nodes of a weighted and undirected graph. It is based on a Markov-chain model of random walk through the database. More precisely, we compute quantities (the average commute time, the pseudoinverse of the Laplacian matrix of the graph, etc.) that provide similarities between any pair of nodes, having the nice property of increasing when the number of paths connecting those elements increases and when the "length" of paths decreases. It turns out that the square root of the average commute time is a Euclidean distance and that the pseudoinverse of the Laplacian matrix is a kernel matrix (its elements are inner products closely related to commute times). A principal component analysis (PCA) of the graph is introduced for computing the subspace projection of the node vectors in a manner that preserves as much variance as possible in terms of the Euclidean commute-time distance. This graph PCA provides a nice interpretation to the "Fiedler vector," widely used for graph partitioning. The model is evaluated on a collaborative-recommendation task where suggestions are made about which movies people should watch based upon what they watched in the past. Experimental results on the MovieLens database show that the Laplacian-based similarities perform well in comparison with other methods. The model, which nicely fits into the so-called "statistical relational learning" framework, could also be used to compute document or word similarities, and, more generally, it could be applied to machine-learning and pattern-recognition tasks involving a relational database     

大规模句子相似度计算方法

如何根据源语言文本从大规模语料库中找出其最相近的翻译实例,即句子相似度计算,是基于实例翻译方法的关键问题之一.本文提出一种多层次句子相似度计算方法首先基于句子的词表层特征和信息熵从大规模语料库中选择出少量候选实例,然后针对这些候选实例进行泛化匹配,从而计算出相似句子.在多策略机器翻译系统IHSMTS中的实验表明,当语料规模为20万英汉句对时,系统提取相似句子的召回率达96%,准确率达90%,充分说明了本文算法的有效性.