A stable graph layout algorithm for processes

Process mining enables organizations to analyze data about their (business) processes. Visualization is key to gaining insight into these processes and the associated data. Process visualization requires a high‐quality graph layout that intuitively represents the semantics of the process. Process analysis additionally requires interactive filtering to explore the process data and process graph. The ideal process visualization therefore provides a high‐quality, intuitive layout and preserves the mental map of the user during the visual exploration. The current industry standard used for process visualization does not satisfy either of these requirements. In this paper, we propose a novel layout algorithm for processes based on the Sugiyama framework. Our approach consists of novel ranking and order constraint algorithms and a novel crossing minimization algorithm. These algorithms make use of the process data to compute stable, high‐quality layouts. In addition, we use phased animation to further improve mental map preservation. Quantitative and qualitative evaluations show that our approach computes layouts of higher quality and preserves the mental map better than the industry standard. Additionally, our approach is substantially faster, especially for graphs with more than 250 edges.     

树结构在N体问题中的应用*

N体问题的数值模拟在每个时间步都需要计算每对粒子之间的相互作用,其复杂度为O(N2).采用树结构代码不仅减少了存储开销,而且更有利于快速计算和并行划分.Barnes-Hut算法(BHA)和快速多极子方法(FMM)都是基于树结构的快速算法.BHA可快速计算各点受到的场力,计算复杂度为O(N log N),但计算精度通常只有1%;FMM通过层次划分和位势函数的多极子展开计算各点位势,其复杂度为O(N),却能达到任意精度.数值结果表明,树结构的并行效果也很好.     

Smashing peacocks further: drawing quasi-trees from biconnected components

We extend the popular force-directed approach to network (or graph) layout to allow separation constraints, which enforce a minimum horizontal or vertical separation between selected pairs of nodes. This simple class of linear constraints is expressive enough to satisfy a wide variety of application-specific layout requirements, including: layout of directed graphs to better show flow; layout with non-overlapping node labels; and layout of graphs with grouped nodes (called clusters). In the stress majorization force-directed layout process, separation constraints can be treated as a quadratic programming problem. We give an incremental algorithm based on gradient projection for efficiently solving this problem. The algorithm is considerably faster than using generic constraint optimization techniques and is comparable in speed to unconstrained stress majorization. We demonstrate the utility of our technique with sample data from a number of practical applications including gene-activation networks, terrorist networks and visualization of high-dimensional data     

基于PageRank的网络布局算法

基于力导向模型的网络布局算法由于其布局结果直观并且便于分析所以在网络可视化中占有举足轻重的地位。但是当前的网络布局算法在面对大规模网络数据的时候通常不容易在较短时间内获取一个高质量的布局结果。本文提出了一个基于PageRank的力导向模型的算法。该算法引入了PageRank来完善节点的重力和斥力计算以改善布局质量；并且引入节点中心性来预估初始布局中节点的位置；同时,又提出了基于PageRank的自适应步长用来平衡布局的效率和质量。最后为了有效的减少布局算法在面对大规模网络数据时的计算时间,本文设计了一个基于CUDA的灵活的CPU+GPU异构并行计算框架。通过对不同类型和不同规模的网络数据集的实验,该算法能够产出一个符合美学标准的高质量布局,并且在同样的硬件条件下,本文所提出的优化方案相比于原始算法速度最大提高了58倍。     

Efficient BVH‐based Collision Detection Scheme with Ordering and Restructuring

Bounding volume hierarchy (BVH) has been widely adopted as the acceleration structure in broad‐phase collision detection. Previous state‐of‐the‐art BVH‐based collision detection approaches exploited the spatio‐temporal coherence of simulations by maintaining a bounding volume test tree (BVTT) front. A major drawback of these algorithms is that large deformations in the scenes decrease culling efficiency and slow down collision queries. Moreover, for front‐based methods, the inefficient caching on GPU caused by the arbitrary layout of BVH and BVTT front nodes becomes a critical performance issue. We present a fast and robust BVH‐based collision detection scheme on GPU that addresses the above problems by ordering and restructuring BVHs and BVTT fronts. Our techniques are based on the use of histogram sort and an auxiliary structure BVTT front log, through which we analyze the dynamic status of BVTT front and BVH quality. Our approach efficiently handles inter‐ and intra‐object collisions and performs especially well in simulations where there is considerable spatio‐temporal coherence. The benchmark results demonstrate that our approach is significantly faster than the previous BVH‐based method, and also outperforms other state‐of‐the‐art spatial subdivision schemes in terms of speed.     

Visual exploration of complex time-varying graphs

Quasi-trees, namely graphs with tree-like structure, appear in many application domains, including bioinformatics and computer networks. Our new SPF approach exploits the structure of these graphs with a two-level approach to drawing, where the graph is decomposed into a tree of biconnected components. The low-level biconnected components are drawn with a force-directed approach that uses a spanning tree skeleton as a starting point for the layout. The higher-level structure of the graph is a true tree with meta-nodes of variable size that contain each biconnected component. That tree is drawn with a new area-aware variant of a tree drawing algorithm that handles high-degree nodes gracefully, at the cost of allowing edge-node overlaps. SPF performs an order of magnitude faster than the best previous approaches, while producing drawings of commensurate or improved quality     

PixelSNE: Pixel‐Aligned Stochastic Neighbor Embedding for Efficient 2D Visualization with Screen‐Resolution Precision

Embedding and visualizing large‐scale high‐dimensional data in a two‐dimensional space is an important problem, because such visualization can reveal deep insights of complex data. However, most of the existing embedding approaches run on an excessively high precision, even when users want to obtain a brief insight from a visualization of large‐scale datasets, ignoring the fact that in the end, the outputs are embedded onto a fixed‐range pixel‐based screen space. Motivated by this observation and directly considering the properties of screen space in an embedding algorithm, we propose Pixel‐Aligned Stochastic Neighbor Embedding (PixelSNE), a highly efficient screen resolution‐driven 2D embedding method which accelerates Barnes‐Hut tree‐based t‐distributed stochastic neighbor embedding (BH‐SNE), which is known to be a state‐of‐the‐art 2D embedding method. Our experimental results show a significantly faster running time for PixelSNE compared to BH‐SNE for various datasets while maintaining comparable embedding quality.     

一种多策略引导的电磁场优化算法

针对标准电磁场优化算法容易陷入局部极值点、收敛精度差等问题,提出了一种多策略引导的电磁场优化算法。算法中粒子受到三种不同来源的引斥力,在迭代过程中通过计算每种移动策略的临代电差、累计电差和综合电差来决定粒子的引导方式,并通过概率变异算法来避免陷入局部最优解。在经典的基准测试函数上,对新算法与其他算法的测试结果比较进行分析,结果表明该算法具有更高的求解精度和更快的计算速度。     

SetCoLa: High‐Level Constraints for Graph Layout

Constraints enable flexible graph layout by combining the ease of automatic layout with customizations for a particular domain. However, constraint‐based layout often requires many individual constraints defined over specific nodes and node pairs. In addition to the effort of writing and maintaining a large number of similar constraints, such constraints are specific to the particular graph and thus cannot generalize to other graphs in the same domain. To facilitate the specification of customized and generalizable constraint layouts, we contribute SetCoLa: a domain‐specific language for specifying high‐level constraints relative to properties of the backing data. Users identify node sets based on data or graph properties and apply high‐level constraints within each set. Applying constraints to node sets rather than individual nodes reduces specification effort and facilitates reapplication of customized layouts across distinct graphs. We demonstrate the conciseness, generalizability, and expressiveness of SetCoLa on a series of real‐world examples from ecological networks, biological systems, and social networks.     

A Subspace Method for Fast Locally Injective Harmonic Mapping

We present a fast algorithm for low‐distortion locally injective harmonic mappings of genus 0 triangle meshes with and without cone singularities. The algorithm consists of two portions, a linear subspace analysis and construction, and a nonlinear non‐convex optimization for determination of a mapping within the reduced subspace. The subspace is the space of solutions to the Harmonic Global Parametrization (HGP) linear system [BCW17], and only vertex positions near cones are utilized, decoupling the variable count from the mesh density. A key insight shows how to construct the linear subspace at a cost comparable to that of a linear solve, extracting a very small set of elements from the inverse of the matrix without explicitly calculating it. With a variable count on the order of the number of cones, a tangential alternating projection method [HCW17] and a subsequent Newton optimization [CW17] are used to quickly find a low‐distortion locally injective mapping. This mapping determination is typically much faster than the subspace construction. Experiments demonstrating its speed and efficacy are shown, and we find it to be an order of magnitude faster than HGP and other alternatives.     

基于单字符注意力的全品类鲁棒车牌识别

复杂场景下的高精度车牌识别仍然存在着许多挑战,除了光照、分辨率不可控和运动模糊等因素导致的车牌图像质量低之外,还包括车牌品类多样产生的行数不一和字数不一等困难,以及因拍摄角度多样出现的大倾角等问题.针对这些挑战,提出了一种基于单字符注意力的场景鲁棒的高精度车牌识别算法,在无单字符位置标签信息的情况下,使用注意力机制对车牌全局特征图进行单字符级特征分割,以处理多品类车牌和倾斜车牌中的二维字符布局问题.另外,该算法通过使用共享参数的多分支结构代替现有算法的串行解码结构,降低了分类头参数量并实现了并行化推理.实验结果表明,该算法在公开车牌数据集上实现了超越现有算法的精度,同时具有较快的识别速度.     

基于GPU的大尺度网络布局显示

复杂网络的可视化是复杂网络研究中的重要手段.随着Web2.0时代和大数据时代的来临,作为研究对象的复杂网络的规模越来越大,这对复杂网络可视化布局算法的布局效果和运算速度提出了新的挑战.本文针对复杂网络布局的力导引算法,从布局效果和算法效率两方面对该算法进行了改进和实现.布局效果方面,利用复杂网络中的关节点,对网络数据进行抽象合并,从而实现分层次的网络布局显示.算法效率方面,针对压缩后的网络采用具有强大浮点运算能力的GPU进行计算,对力导引算法需要斥力计算、引力计算和坐标更新三个部分均实现了基于GPU的并行计算,大大提高了计算效率.     

Bayesian Collaborative Denoising for Monte Carlo Rendering

The stochastic nature of Monte Carlo rendering algorithms inherently produces noisy images. Essentially, three approaches have been developed to solve this issue: improving the ray‐tracing strategies to reduce pixel variance, providing adaptive sampling by increasing the number of rays in regions needing so, and filtering the noisy image as a post‐process. Although the algorithms from the latter category introduce bias, they remain highly attractive as they quickly improve the visual quality of the images, are compatible with all sorts of rendering effects, have a low computational cost and, for some of them, avoid deep modifications of the rendering engine. In this paper, we build upon recent advances in both non‐local and collaborative filtering methods to propose a new efficient denoising operator for Monte Carlo rendering. Starting from the local statistics which emanate from the pixels sample distribution, we enrich the image with local covariance measures and introduce a nonlocal bayesian filter which is specifically designed to address the noise stemming from Monte Carlo rendering. The resulting algorithm only requires the rendering engine to provide for each pixel a histogram and a covariance matrix of its color samples. Compared to state‐of‐the‐art sample‐based methods, we obtain improved denoising results, especially in dark areas, with a large increase in speed and more robustness with respect to the main parameter of the algorithm. We provide a detailed mathematical exposition of our bayesian approach, discuss extensions to multiscale execution, adaptive sampling and animated scenes, and experimentally validate it on a collection of scenes.     

A real-time vision system using an integrated memory array processor prototype

This paper describes a real-time vision system (RVS) architecture and performance and its use of an integrated memory array processor (IMAP) prototype. This prototype integrates eight 8-bit processors and a 144-kbit SRAM on a single chip. The RVS was developed with 64 IMAP prototypes connected in series in a 512 processor-system configuration. A host workstation can access the memory on the IMAP prototypes directly through a random access port. Images are inputted and outputted at high speed through serial access ports. The RVS performance is shown in real-time road-image processing and in a neural network simulation, as well as in low-level image processing algorithms, such as filtering, histograms, discrete cosine transform (DCT), and rotation. The RVS image processing is shown to be much faster than the video rate.     

基于因果图启发式的并行概率规划求解

并行概率规划(PPP)是近年来智能规划领域中的研究热点。在该类问题中,动作具有并发性和不确定性,非常贴近现实问题。然而,现有的两种针对PPP的主要求解方法都有明显的缺点。一种基于模拟抽样,以规划器PROST为代表,但求解速度慢;另一种基于迭代深化,以规划器Glutton为代表,但求解质量差。因此,我们尝试使用高效的启发式搜索方法来求解这类问题。目前,因果图启发式(CGH)是启发式规划方法中的佼佼者。考虑到PPP问题采用RDDL语言来描述,其中的条件概率函数(CPF)非常适合用于构建因果图(CG),所以我们引入因果图来对基于RDDL描述的PPP问题进行启发式求解。本文的主要启发式算法称为CGH_RDDL,整体求解方法是使用rddlsim模拟状态演化以及用CGH_RDDL引导搜索。具体做法是：先从领域描述构建出因果图及领域转换图(DTG);然后根据CG和DTG,计算单个状态变量任意一对取值间的转换代价;接着在rddlsim的模拟演化过程中,由CGH_RDDL推送具有最佳估值的后继状态,其中状态的启发值定义为状态轨迹的转换代价和立即回报值的总和;最后累加在限定轮数内rddlsim状态演化的回报值,即为最终的求解质量。在PPP基准领域上的实验结果表明,在不允许手工干预和参数调整的前提下,本文方法的求解效果要好于PROST和Glutton。更进一步地,与其它的基本启发式相比,CGH_RDDL的求解质量高于随机搜索,求解速度快于爬山法。这表明在经典规划领域中高效的启发式搜索策略可扩展去求解这一类非经典规划问题。而非经典规划问题更具有现实意义和应用前景,更值得探讨先进的规划方法去求解它们。     

Incremental Labelling of Voronoi Vertices for Shape Reconstruction

We present an incremental Voronoi vertex labelling algorithm for approximating contours, medial axes and dominant points (high curvature points) from 2D point sets. Though there exist many number of algorithms for reconstructing curves, medial axes or dominant points, a unified framework capable of approximating all the three in one place from points is missing in the literature. Our algorithm estimates the normals at each sample point through poles (farthest Voronoi vertices of a sample point) and uses the estimated normals and the corresponding tangents to determine the spatial locations (inner or outer) of the Voronoi vertices with respect to the original curve. The vertex classification helps to construct a piece‐wise linear approximation to the object boundary. We provide a theoretical analysis of the algorithm for points non‐uniformly (ε‐sampling) sampled from simple, closed, concave and smooth curves. The proposed framework has been thoroughly evaluated for its usefulness using various test data. Results indicate that even sparsely and non‐uniformly sampled curves with outliers or collection of curves are faithfully reconstructed by the proposed algorithm.     

奇异值分解下在线鲁棒正则化随机网络

在线鲁棒随机权神经网络(OR-RVFLN)具有较好的逼近性、较快的收敛速度、较高的鲁棒性能以及较小的 存储空间. 但是, OR-RVFLN 算法计算过程中会产生矩阵的不适定问题, 使得隐含层输出矩阵的精度较低. 针对这 个问题, 本文提出了奇异值分解下在线鲁棒正则化随机网络(SVD-OR-RRVFLN). 该算法在OR-RVFLN 算法的基础 上, 将正则化项引入到权值的估计中, 并且对隐含层输出矩阵进行奇异值分解; 同时采用核密度估计(KDE) 法, 对 整个SVD-OR-RRVFLN网络的权值矩阵进行更新, 并分析了所提算法的必要性和收敛性. 最后, 将所提的方法应用 于Benchmark数据集和磨矿粒度的指标预测中, 实验结果证实了该算法不仅可以有效地提高模型的预测精度和鲁 棒性能, 而且具有更快的训练速度.     

A tabu search based approach for graph layout

This paper describes an automated tabu search based method for drawing general graph layouts with straight lines. To our knowledge, this is the first time tabu methods have been applied to graph drawing. We formulated the task as a multi-criteria optimization problem with a number of metrics which are used in a weighted fitness function to measure the aesthetic quality of the graph layout. The main goal of this work is to speed up the graph layout process without sacrificing layout quality. To achieve this, we use a tabu search based method that goes through a predefined number of iterations to minimize the value of the fitness function. Tabu search always chooses the best solution in the neighbourhood. This may lead to cycling, so a tabu list is used to store moves that are not permitted, meaning that the algorithm does not choose previous solutions for a set period of time. We evaluate the method according to the time spent to draw a graph and the quality of the drawn graphs. We give experimental results applied on random graphs and we provide statistical evidence that our method outperforms a fast search-based drawing method (hill climbing) in execution time while it produces comparably good graph layouts. We also demonstrate the method on real world graph datasets to show that we can reproduce similar results in a real world setting.     

一个新的MOS模拟单元电路版图的STACK生成方法

提出了一种新的MOS模拟单元电路的STACK版图自动生成方法。该方法将电路网表映射为扩散图,基于扩散图进行电路划分、模板匹配和对称查找。提出的对称查找算法适用于非全对称电路的最大匹配对称结构查找。文中改进了Atallah欧拉路径生成算法,通过增加哑元条保证欧拉路 径的生成。对生成的STACK,采用分布式寄生电容模型计算各个节点的寄生电容,并计算STACK的面积和形状,以确保其能够满足设计要求。     

基于差分演化与猫群算法融合的群体智能算法

提出一种基于差分演化与猫群算法融合的群体智能算法。该算法基于猫群算法的两种行为模式,引进差分演化的思想,根据分组率随机把群体分成两个种群,一个种群执行猫群算法搜寻模式,另一种群执行差分变异模式,算法采用一种信息共享机制,使两个种群在搜索最优解时可以实现协同进化,信息交流。既实现了不同进化模式间的优势互补,又可以增加种群的多样性。对5个基准函数进行仿真实验并分别与DE和CSO进行比较,表明混合算法同时具有全局搜索和局部搜索最优解性能,收敛速度快,计算精度高,更适合用于求解高维复杂函数。