基于GPU的子图匹配优化技术

为了解决图挖掘应用中子图匹配任务的性能问题,本文提出了一种基于图形处理单元(GPU)的顶点预剪枝子图匹配系统(GVSM).GVSM采用黑名单剪枝算法和调度排序来减少冗余搜索.利用前缀树数据结构,GVSM可以对中间结果进行压缩,以便快速索引并降低内存消耗.GVSM将子图匹配的搜索部分卸载到GPU上执行,通过设计软件流水线...     

一种高效挖掘生物网络闭合频繁子图的算法

针对生物网络中频繁子图的挖掘问题,提出了一种基于FP-树结构的MaxFP算法.此算法以代谢路径作为研究对象,在适合于生物网络图简化模型的基础上,采用一种不产生候选集的改进FP-growth算法挖掘生物网络中的闭合频繁子图.此算法考虑了基于频繁项目集的算法应用于网络的缺陷,根据生物网络的特点对FP-growth算法进行了改进.实验证明,提出的MaxFP算法比基于Apriori的频繁模式挖掘算法运行速度快,不仅能挖掘出最大的频繁子图,且能找到更多具有生物意义的频繁子图.     

顶点划分映射算法判定运动链同构

研究机构创新设计中运动链同构判定问题. 依据图论和机构拓扑学原理,提出子块、平方和度、子块关联度等概念;利用拓扑图顶点间连接关系,构造顶点分类集合;提出一种将所有顶点一一划分并两两映射的算法,实现同构识别. 实验结果证明该算法比现有算法效率高. 将算法设计基础理论应用于机构拓扑学,为该领域研究提供新思路     

节点与决策模式两段式映射的子图查询算法

针对大规模图集的子图查询问题,给出了一种基于节点与决策模式映射(NDFM)的索引结构——NDFM-Index,并在此索引结构的基础上提出了一种图集的子图查询算法。NDFM-Index利用图中关键节点所携带的结构信息以及邻居的标号分布,与决策模式形成映射,从而不通过枚举直接得到查询图所包含的索引模式,得到更小的候选集。理论与实验的分析结果表明,该算法不但能避免索引筛选过程中对查询图子图的枚举过程,而且能显著地减小候选集尺寸,进而大大降低查询图与候选集之间的子图同构测试次数,提高查询效率。     

无爪图的泛圈性

证明了如果Ｇ是２连通无爪图，Ｇ不是圈，ｎ＝│Ｖ（Ｇ）│≥９，Ｇ的每个同构于Ａ的导出子图都满足Φ（α，α２）且Ｇ中不含同构于Ｄ的导出子图，则Ｇ是泛圈图或同构于Ｇ１。     

遗传算法在图同构判定中的应用与实现

以简单图作为判断对象,根据遗传算法具有全局快速搜索的特点,将实际问题中的空间解数据编码变成遗传空间的基因型串结构的数据,采用确定型遗传算子选择策略,在有限的运算次数内判断图是否同构,实现基于遗传算法的图同构判定。     

一种解无约束优化问题的新移动渐近线算法

对无约束优化问题,本文提出了一种新的移动渐近线算法.在每次迭代过程中,我们构造一个原问题的移动渐近线函数,由此建立一个简单可分、严格凸的子问题,通过求解子问题获得下降搜索方向,再用线搜索取得搜索步长.文中讨论了算法的参数取值原则,并证明了算法的全局收敛性.数值试验结果表明算法是有效的、适合解大规模的无约束优化问题.     

拆卸与或图生成及其权重不定问题研究

为了高效地规划装配体的拆卸序列,首先利用生成完备可行子装配体的算法构造所有可行的拆卸操作,并以与或图的形式将所有可行的拆卸操作加以表达,对该与或图进行简约,从而构建能够表达所有可行拆卸序列的拆卸与或图;为了基于该拆卸与或图规划拆卸序列,利用广义权重解决了拆卸与或图中有向边上权重不确定的问题,并给出了广义权重的计算方法;最后,通过实例验证了这种拆卸与或图表达拆卸序列的高效性和用于拆卸序列规划的可行性和有效性.结果表明拆卸与或图是一种可用于拆卸序列规划的高效模型.     

公交换乘最短路径算法研究

改进的Dijkstra算法和Floyd算法是求两点间最短距离和最短路径的最简单有效的方法。但是当图的顶点个数为上万或者几十万时,计算两点间的最短距离的时间开销将是非常巨大的。利用加权图的子图来解决这一问题。     

图的度量维数问题的0-1蚁群条件着色分辨算法研究

图的度量维数问题（MDP）是一类在机器导航、声呐系统布置、化学、数据分类等领域有重要应用的组合优化问题．针对该问题,本文通过引入图的分辨表存储结构,建立了非线性求解模型;同时,通过改进现有蚁群算法的参数设计,利用全局搜索和局部搜索相结合的策略,建立了求解模型的改进型蚁群算法．数值对比分析验证了算法的有效性：全局搜索和局部搜索的结合较大程度的改进了算法求解质量;在规则图上提高算法求解质量具有一定挑战;与遗传算法计算结果相比较,本文提出的算法不仅在求解质量方面有所提升,而且在最坏的情况下能为图提供极小分辨集. 最后,本文探索了部分算法参数对算法求解质量的影响,并给出了进一步研究课题．     

Review of tools and algorithms for network motif discovery in biological networks

Network motifs are recurrent and over‐represented patterns having biological relevance. This is one of the important local properties of biological networks. Network motif discovery finds important applications in many areas such as functional analysis of biological components, the validity of network composition, classification of networks, disease discovery, identification of unique subunits etc. The discovery of network motifs is a computationally challenging task due to the large size of real networks, and the exponential increase of search space with respect to network size and motif size. This problem also includes the subgraph isomorphism check, which is Nondeterministic Polynomial (NP)‐complete. Several tools and algorithms have been designed in the last few years to address this problem with encouraging results. These tools and algorithms can be classified into various categories based on exact census, mapping, pattern growth, and so on. In this study, critical aspects of network motif discovery, design principles of background algorithms, and their functionality have been reviewed with their strengths and limitations. The performances of state‐of‐art algorithms are discussed in terms of runtime efficiency, scalability, and space requirement. The future scope, research direction, and challenges of the existing algorithms are presented at the end of the study.Inspec keywords: computational complexity, graph theory, biology, search problemsOther keywords: network size, motif size, network motif discovery, biological networks, network composition, recurrent patterns, over‐represented patterns, local properties, search space, subgraph isomorphism check, NP‐complete problem, NP‐complete problem, exact census, design principles, background algorithms, runtime efficiency, space requirement     

基于静态特征的硬件木马检测

分析了集成电路全球化设计、制造致使集成电路易被植入硬件木马(HT)从而使其存在遭受恶意攻击隐患的硬件安全形势,以及现有硬件木马检测方法的技术特点,在此基础上提出了一种基于静态特征的硬件木马检测新方法——HTChecker。HTChecker基于硬件木马的静态特征利用子图同构技术来检测木马。与其他的检测方法相比,它可以快速精确地找出已知特征的硬件木马。为了不受限于机器内存的大小,该方法借助图数据库来存储电路,这样它对超大规模的电路也可以进行检测。使用ISCAS’89和OpenCores benchmark电路对HTChecker进行了评估,木马电路被随机地插入到这些电路中。实验结果显示HTChecker可以快速精确地找出木马,并且不需要"Golden Chip"的辅助。HTChecker可以有效地处理实际的VLSI设计。     

探索Euler生成子图边数的一种方法

关于超欧拉图的欧拉生成子图(spanning eulerian subgraph)的边数问题,P,A．Catlin、HongJian Lai、Zhi-Hong Chen等人提出若干问题。本文给出了探索超欧拉图的欧拉生成子图边数的一种方法。     

Color constancy based on texture pyramid matching and regularized local regression

Considering that no single algorithm available is universal in color constancy, we propose an effective combination approach using a texture-based matching strategy and a local regression with prior-knowledge regularization. To represent the images, we construct a texture pyramid using an integrated Weibull distribution. Then we define an image similarity measure to search for the K most similar images of the test image. To combine the single algorithms, we integrate prior knowledge into a regularized local regression in a decorrelated color space. Regression weights are obtained on these similar images, and the regularization is implemented by the frequency ratio of the best single algorithm. Experiments on two real world datasets show our approach outperforms the state-of-the-art single algorithms and popular combination approaches with a performance increase of at least 29% compared to the best-performing single algorithm w.r.t median angular error.     

Vertex Cover Optimization Using a Novel Graph Decomposition Approach

The minimum vertex cover problem (MVCP) is a well-known combinatorial optimization problem of graph theory. The MVCP is an NP (nondeterministic polynomial) complete problem and it has an exponential growing complexity with respect to the size of a graph. No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale. However, several algorithms are proposed that solve the problem approximately in a short polynomial time scale. Such algorithms are useful for large size graphs, for which exact solution of MVCP is impossible with current computational resources. The MVCP has a wide range of applications in the fields like bioinformatics, biochemistry, circuit design, electrical engineering, data aggregation, networking, internet traffic monitoring, pattern recognition, marketing and franchising etc. This work aims to solve the MVCP approximately by a novel graph decomposition approach. The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures. A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths. In order to reduce complexity of the algorithm a new strategy is also proposed. The reduction strategy can be used for any algorithm solving MVCP. Based on the graph decomposition and the reduction strategy, two algorithms are formulated to approximately solve the MVCP. These algorithms are tested using well known standard benchmark graphs. The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.     

An optimal and a heuristic algorithm for the single-item retrieval problem in puzzle-based storage systems with multiple escorts

Puzzle-based storage systems consist of densely stored unit loads on a square grid. The problem addressed in this paper is to retrieve a stored unit load from a puzzle-based storage using the minimum number of item moves. While previous research contributed optimal algorithms for only up to two empty locations (escorts), our approach solves configurations where multiple empty locations are arbitrarily positioned in the grid. The problem is formulated as a state space problem and solved to optimality using an exact search algorithm. To reduce the search space, we derive bounds on the number of eligible empty locations and develop several search-guiding estimate functions. Furthermore, we present a heuristic variant of the search algorithm to solve larger problem instances. We evaluate both solution algorithms on a large set of problem instances. Our computational results show that the algorithms clearly outperform existing approaches where they are applicate and solve more general configurations, which could not be solved to optimality before. The heuristic variant efficiently yields high-quality solutions for significantly larger instances of practically relevant size.     

Parallel Optimization of Program Instructions Using Genetic Algorithms

This paper describes an efficient solution to parallelize software program instructions, regardless of the programming language in which they are written. We solve the problem of the optimal distribution of a set of instructions on available processors. We propose a genetic algorithm to parallelize computations, using evolution to search the solution space. The stages of our proposed genetic algorithm are: The choice of the initial population and its representation in chromosomes, the crossover, and the mutation operations customized to the problem being dealt with. In this paper, genetic algorithms are applied to the entire search space of the parallelization of the program instructions problem. This problem is NP-complete, so there are no polynomial algorithms that can scan the solution space and solve the problem. The genetic algorithm-based method is general and it is simple and efficient to implement because it can be scaled to a larger or smaller number of instructions that must be parallelized. The parallelization technique proposed in this paper was developed in the C# programming language, and our results confirm the effectiveness of our parallelization method. Experimental results obtained and presented for different working scenarios confirm the theoretical results, and they provide insight on how to improve the exploration of a search space that is too large to be searched exhaustively.     

Efficient Flexible M-Tree Bulk Loading Using FastMap and Space-Filling Curves

Many database applications currently deal with objects in a metric space. Examples of such objects include unstructured multimedia objects and points of interest (POIs) in a road network. The M-tree is a dynamic index structure that facilitates an efficient search for objects in a metric space. Studies have been conducted on the bulk loading of large datasets in an M-tree. However, because previous algorithms involve excessive distance computations and disk accesses, they perform poorly in terms of their index construction and search capability. This study proposes two efficient M-tree bulk loading algorithms. Our algorithms minimize the number of distance computations and disk accesses using FastMap and a space-filling curve, thereby significantly improving the index construction and search performance. Our second algorithm is an extension of the first, and it incorporates a partitioning clustering technique and flexible node architecture to further improve the search performance. Through the use of various synthetic and real-world datasets, the experimental results demonstrated that our algorithms improved the index construction performance by up to three orders of magnitude and the search performance by up to 20.3 times over the previous algorithm.