Fast,accurate call graph profiling

Existing methods for call graph profiling, such as that used by gprof, deal badly with programs that have shared subroutines, mutual recursion, higher‐order functions, or dynamic method binding. This article discusses a way of improving the accuracy of a call graph profile by collecting more information during execution, without significantly increasing the overhead of profiling. The method is based on keeping track of a context, consisting of the set of subroutines that are active at a particular moment during execution, together with the calling arcs between these subroutines. The profiler records the time spent in each context during execution of the program, and thus obtains an accurate measurement of the total time during which each subroutine was active. By recording arc information for only the most recent activation of each subroutine, it is possible to arrange that even recursive programs give rise to a finite number of these contexts, and in typical real programs, the number of distinct contexts remains manageably small. The data can be collected efficiently during execution by constructing a finite‐state machine whose states correspond to contexts, so that when a context is entered for a second or subsequent time, only a single access of a hash table is needed to update the state of the profiling monitor. Copyright © 2003 John Wiley & Sons, Ltd.     

Efficient and good Delaunay meshes from random points

We present a Conforming Delaunay Triangulation (CDT) algorithm based on maximal Poisson disk sampling. Points are unbiased, meaning the probability of introducing a vertex in a disk-free subregion is proportional to its area, except in a neighborhood of the domain boundary. In contrast, Delaunay refinement CDT algorithms place points dependent on the geometry of empty circles in intermediate triangulations, usually near the circle centers. Unconstrained angles in our mesh are between 30° and 120°, matching some biased CDT methods. Points are placed on the boundary using a one-dimensional maximal Poisson disk sampling. Any triangulation method producing angles bounded away from 0° and 180° must have some bias near the domain boundary to avoid placing vertices infinitesimally close to the boundary.Random meshes are preferred for some simulations, such as fracture simulations where cracks must follow mesh edges, because deterministic meshes may introduce non-physical phenomena. An ensemble of random meshes aids simulation validation. Poisson-disk triangulations also avoid some graphics rendering artifacts, and have the blue-noise property.We mesh two-dimensional domains that may be non-convex with holes, required points, and multiple regions in contact. Our algorithm is also fast and uses little memory. We have recently developed a method for generating a maximal Poisson distribution of n output points, where n=Θ(Area/r²) and r is the sampling radius. It takes O(n) memory and O(nlogn) expected time; in practice the time is nearly linear. This, or a similar subroutine, generates our random points. Except for this subroutine, we provably use O(n) time and space. The subroutine gives the location of points in a square background mesh. Given this, the neighborhood of each point can be meshed independently in constant time. These features facilitate parallel and GPU implementations. Our implementation works well in practice as illustrated by several examples and comparison to Triangle.     

Ehlers pan-sharpening performance enhancement using HCS transform for n-band data sets

The Ehlers fusion method, which combines a standard intensity-hue-saturation (IHS) transform with fast Fourier transform filtering, is a high spectral characteristics preservation algorithm for multitemporal and multisensor data sets. However, for data sets of more than three bands, the fusion process is complicated, because only every three bands are fused repeatedly for multiple times until all bands are fused. The hyper-spherical colour sharpening (HCS) fusion method can fuse a data set with an arbitrary number of bands. The HCS approach uses a transform between an n-dimensional Cartesian space and an n-dimensional hyper-spherical space to get one single intensity component and n ? 1 angles. Moreover, from a structural point of view, the hyper-spherical colour space is very similar to the IHS colour space. Hence, we propose to combine the Ehlers fusion with an HCS transform to fuse n-band data sets with high spectral information preservation, even hyper-spectral images. A WorldView-2 data set including a panchromatic and eight multispectral bands is used for demonstrating the effectiveness and quality of the new Ehlers –HCS fusion. The WorldView-2 image covers different landscapes such as agriculture, forest, water and urban areas. The fused images are visually and quantitatively analysed for spectral preservation and spatial improvement. Pros and cons of the applied fusion methods are related to the analysed different landscapes. Overall, the Ehlers –HCS method shows the efficacy for n-band fusion.     

Selection, Routing, and Sorting on the Star Graph

We consider the problems of selection, routing, and sorting on ann-star graph (withn! nodes), an interconnection network which has been proven to possess many special properties. We identify a tree like subgraph (which we call a “(k, 1,k) chain network”) of the star graph which enables us to design efficient algorithms for the above mentioned problems. We present an algorithm that performs a sequence ofnprefix computations inO(n²) time. This algorithm is used as a subroutine in our other algorithms. We also show that sorting can be performed on then-star graph in timeO(n³) and that selection of a set of uniformly distributednkeys can be performed inO(n²) time with high probability. Finally, we also present a deterministic (nonoblivious) routing algorithm that realizes any permutation inO(n³) steps on then-star graph. There exists an algorithm in the literature that can perform a single prefix computation inO(nlgn) time. The best-known previous algorithm for sorting has a run time ofO(n³lgn) and is deterministic. To our knowledge, the problem of selection has not been considered before on the star graph.     

Sorting-Based Selection Algorithms for Hypercubic Networks

This paper presents several deterministic algorithms for selecting the k th largest record from a set of n records on any n -node hypercubic network. All of the algorithms are based on the selection algorithm of Cole and Yap, as well as on various sorting algorithms for hypercubic networks. Our fastest algorithm runs in O( lg n lg ^* n) time, very nearly matching the trivial lower bound. Previously, the best upper bound known for selection was O( lg n lg lg n) . A key subroutine in our O( lg n lg ^* n) time selection algorithm is a sparse version of the Sharesort algorithm that sorts n records using p processors, , in O( lg n ( lg lg p - lg lg (p/n) ) ² ) time. Received March 23, 1994; revised October 30, 1997.     

利用语义词典Web挖掘语言模型的无指导译文消歧

为了解决困扰词义及译文消歧的数据稀疏及知识获取问题,提出一种基于Web利用n-gram统计语言模型进行消歧的方法.在提出词汇语义与其n-gram语言模型存在对应关系假设的基础上,首先利用Hownet建立中文歧义词的英文译文与知网DEF的对应关系并得到该DEF下的词汇集合,然后通过搜索引擎在Web上搜索,并以此计算不同DEF中词汇n-gram出现的概率,然后进行消歧决策.在国际语义评测SemEval-2007中的Multilingual Chinese English Lexical Sample Task测试集上的测试表明,该方法的P_mar值为55.9%,比其上该任务参评最好的无指导系统性能高出12.8%.     

An interval‐based temporal algebra based on binary encoding of point relations

This paper presents a method for representing temporal interval relations using a bit‐encoded form of the relationships between interval end points. The set of bit patterns for each interval relationship yields a unique, single‐byte signature that forms the basis of a binary temporal algebra. Also presented is a matrix multiplication algorithm for computing transitive relations based on the definition of sum and product operations for the bit‐encoded relation signatures. This bit‐encoding encompasses the representation of unknown relations between end points of two intervals and captures ambiguities within a temporal system while providing an efficient binary algebra. Finally, an algorithm to compute the transitive closure over a set of intervals forming a temporal system is presented. The algorithm's complexity is analyzed and is O(n³), worst case, where n is the number of temporal intervals within the system. Empirical observations indicate that the closure algorithm completes in O(n²) time, on average. The small memory footprint for the bit‐code, the algorithmic transitive relation calculation, and the closure algorithm, together, form an efficient method for providing machine‐based temporal reasoning capabilities. ©2000 John Wiley & Sons, Inc.     

Lumped model of a non-linear distributed system by finite element method

The finite element method has been used to find an approximate lumped parameter model of a non-linear distributed parameter system. A one dimensional non-linear dispersion system is considered. The space domain is divided into a finite set of k elements. Each element, has n nodes. Within each element the concentration is represented by C(x,t)^(e) = [N][C] ^T where [N] = [n₁(x),n₂(x), [tdot] n_n(x)] and [C] = [C₁(t),C₂(t), [tdot] C_n(t)]. By using Galerkin's criterion a set of (k × n ? n+ 1) first order differential equations are obtained for C_i(t). These equations are solved by an iterative method. The concepts are illustrated by an example taking five three-node elements in the space domain. The results are compared with those obtained by a finite difference method. It is shown that the finite element method can be used effectively in modelling of a distributed system by a lumped system.     

Multi-way set enumeration in weight tensors

The analysis of n-ary relations receives attention in many different fields, for instance biology, web mining, and social studies. In the basic setting, there are n sets of instances, and each observation associates n instances, one from each set. A common approach to explore these n-way data is the search for n-set patterns, the n-way equivalent of itemsets. More precisely, an n-set pattern consists of specific subsets of the n instance sets such that all possible associations between the corresponding instances are observed in the data. In contrast, traditional itemset mining approaches consider only two-way data, namely items versus transactions. The n-set patterns provide a higher-level view of the data, revealing associative relationships between groups of instances. Here, we generalize this approach in two respects. First, we tolerate missing observations to a certain degree, that means we are also interested in n-sets where most (although not all) of the possible associations have been recorded in the data. Second, we take association weights into account. In fact, we propose a method to enumerate all n-sets that satisfy a minimum threshold with respect to the average association weight. Technically, we solve the enumeration task using a reverse search strategy, which allows for effective pruning of the search space. In addition, our algorithm provides a ranking of the solutions and can consider further constraints. We show experimental results on artificial and real-world datasets from different domains.     

Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems

Abstract. There is an error in our paper ``An Approximation Algorithm for Minimum-Cost Vertex- Connectivity Problems' (Algorithmica (1997), 18:21—43). In that paper we considered the following problem: given an undirected graph and values r _ij for each pair of vertices i and j , find a minimum-cost set of edges such that there are r _ij vertex-disjoint paths between vertices i and j . We gave approximation algorithms for two special cases of this problem. Our algorithms rely on a primal—dual approach which has led to approximation algorithms for many edge-connectivity problems. The algorithms work in a series of stages; in each stage an augmentation subroutine augments the connectivity of the current solution. The error is in a lemma for the proof of the performance guarantee of the augmentation subroutine. In the case r _ij = k for all i,j , we described a polynomial-time algorithm that claimed to output a solution of cost no more than 2 H (k) times optimal, where H = 1 + 1/2 + · · · + 1/n . This result is erroneous. We describe an example where our primal—dual augmentation subroutine, when augmenting a k -vertex connected graph to a (k+1) -vertex connected graph, gives solutions that are a factor Ω(k) away from the minimum. In the case r _ij ∈ {0,1,2} for all i,j , we gave a polynomial-time algorithm which outputs a solution of cost no more than three times the optimal. In this case we prove that the statement in the lemma that was erroneous for the k -vertex connected case does hold, and that the algorithm performs as claimed.     

Computation of the padé table

Simple recursion formulas are presented for computing the coefficients in the Padé table of a power series f(x). A Fortran subroutine for the computation is given in an Appendix, where a second subroutine for evaluating the elements for any x is also given. Two applications are mentioned. The assumption is made that the Padé table is normal.     

粗糙集多目标并行属性约简算法

粗糙集理论(RST)中,求解最小属性约简MAR (minimal attribute reduction)是一种NP-难(non-deterministic polynomialhard)组合优化问题.蚁群优化算法ACO(antcolonyoptimization)是进化算法中的一种启发式全局优化算法,粗糙集理论与ACO相结合,是求解属性约简的一种有效、可行的方式.针对蚁群优化算法易于陷入局部最优解、收敛速度慢等问题,首先以一种改进的信息增益率作为启发信息,提出了冗余检测机制,对每个被选属性和每代最优约简集合进行冗余检测,并提出了概率提前计算机制,可避免每只蚂蚁在搜索过程中相同路径上的信息反复计算;针对大数据集的属性约简问题,考虑到蚁群优化算法具有并行能力以及粗糙集中“等价类”计算的可并行性,提出一种将ACO与云计算相结合用于求解大数据集的属性约简算法,在此基础上,进一步提出一种多目标并行求解方案.该方案可以同时计算出其余属性相对于当前属性或约简集合的重要度.实验结果表明,该算法在处理大数据的情况下能够得到最小属性约简,计算属性重要度的时间复杂度由O(n2)降至O(|n|).     

Selective sampling for approximate clustering of very large data sets

A key challenge in pattern recognition is how to scale the computational efficiency of clustering algorithms on large data sets. The extension of non‐Euclidean relational fuzzy c‐means (NERF) clustering to very large (VL = unloadable) relational data is called the extended NERF (eNERF) clustering algorithm, which comprises four phases: (i) finding distinguished features that monitor progressive sampling; (ii) progressively sampling from a N × N relational matrix R_N to obtain a n × n sample matrix R_n; (iii) clustering R_n with literal NERF; and (iv) extending the clusters in R_n to the remainder of the relational data. Previously published examples on several fairly small data sets suggest that eNERF is feasible for truly large data sets. However, it seems that phases (i) and (ii), i.e., finding R_n, are not very practical because the sample size n often turns out to be roughly 50% of n, and this over‐sampling defeats the whole purpose of eNERF. In this paper, we examine the performance of the sampling scheme of eNERF with respect to different parameters. We propose a modified sampling scheme for use with eNERF that combines simple random sampling with (parts of) the sampling procedures used by eNERF and a related algorithm sVAT (scalable visual assessment of clustering tendency). We demonstrate that our modified sampling scheme can eliminate over‐sampling of the original progressive sampling scheme, thus enabling the processing of truly VL data. Numerical experiments on a distance matrix of a set of 3,000,000 vectors drawn from a mixture of 5 bivariate normal distributions demonstrate the feasibility and effectiveness of the proposed sampling method. We also find that actually running eNERF on a data set of this size is very costly in terms of computation time. Thus, our results demonstrate that further modification of eNERF, especially the extension stage, will be needed before it is truly practical for VL data. © 2008 Wiley Periodicals, Inc.     

A FORTRAN decoder and evaluator for use at operation time

Except for normative components, the calculation of which is sufficiently involved to require a separate subroutine, the compositional “derived variables” of chemical petrology may be cast readily in the form of simple arithmetic expressions. With regard to the design of petrographic data bases and their associated information systems, the practical question is whether these should be processed by the base builder, so that the values of each derived variable are incorporated in the base, by an ad hoc subroutine linked to the information system prior to each retrieval or reduction, or by permanent elements of the information system. The third option requires intrinsic capability for decoding and evaluating expressions received as character strings at operation time. Subroutines DKDXPR and EVLXPR provide that capability. Calling program IMDEVL provides a convenient conversational device for testing DKDXPR and EVLXPR.     

Pattern recognition by sequential sweeping along preferred directions†

This paper deals with a novel method of pattern recognition, in which recognition is effected by sequential sweeping along preferred directions. The chosen set of measurement directions (x ₁, x ₂, … x _n) are first ordered according to preference and then the axes are swept sequentially in that order. An algorithm is proposed which gives a code representation for the pattern clusters in an n-dimensional pattern space. Two models are proposed for the recognizer. It is shown that the method is capable of 100% recognition of learning patterns, under the assumption that no two patterns belonging to different categories occupy the same pattern point in the pattern space.

A further advantage of the method is that out of an initially chosen set of measurements (characteristics) the recognizer makes use only of an important sub-set. Thus a sort of ‘measurement selection ’ is inherent in this type of pattern recognizer.     

Ensuring Fault-Tolerance in Distributed Media

A method for ensuring system fault-tolerance and guaranteed data access based on a model of distributed data storage with controlled redundancy is considered. A data file is represented as a set of nparts, each of size 1/kof the source file, so that the source file can be generated from any kparts (k<= n). The cardinality of the set may vary by constructing new (or by deleting the existing) parts, i.e., without modifying the existing parts, so that the source file can still be generated from any kparts. The file partitioning and assembly algorithms are based on the theory of finite Galois fields GF. A file is represented as a sequence of k-dimensional vectors over a GF. Every fragment is a sequence of projections of these vectors onto a k-dimensional vector (chosen for the given fragment) over the GF. In the paper, several implementations of the model are presented. For each of these implementations, the results of performance on the Celeron-450 processor are obtained and analyzed to determine their range of application.     

Hermite variational implicit surface reconstruction

We propose a new technique for reconstructing surfaces from a large set of unorganized 3D data points and their associated normal vectors. The surface is represented as the zero level set of an implicit vol-ume model which fits the data points and normal constraints. Compared with variational implicit sur-faces,we make use of surface normal vectors at data points directly in the implicit model and avoid of introducing manufactured off-surface points. Given n surface point/normal pairs,the proposed method only needs to solve an n×n positive definite linear system. It allows fitting large datasets effectively and robustly. We demonstrate the performance of the proposed method with both globally supported and compactly supported radial basis functions on several datasets.     

Communication-efficient parallel algorithms for distributed random-access machines

This paper introduces a model for parallel computation, called thedistributed randomaccess machine (DRAM), in which the communication requirements of parallel algorithms can be evaluated. A DRAM is an abstraction of a parallel computer in which memory accesses are implemented by routing messages through a communication network. A DRAM explicitly models the congestion of messages across cuts of the network.We introduce the notion of aconservative algorithm as one whose communication requirements at each step can be bounded by the congestion of pointers of the input data structure across cuts of a DRAM. We give a simple lemma that shows how to shortcut pointers in a data structure so that remote processors can communicate without causing undue congestion. We giveO(lgn)-step, linear-processor, linear-space, conservative algorithms for a variety of problems onn-node trees, such as computing treewalk numberings, finding the separator of a tree, and evaluating all subexpressions in an expression tree. We giveO(lg² n)-step, linear-processor, linear-space, conservative algorithms for problems on graphs of sizen, including finding a minimum-cost spanning forest, computing biconnected components, and constructing an Eulerian cycle. Most of these algorithms use as a subroutine a generalization of the prefix computation to trees. We show that any suchtreefix computation can be performed inO(lgn) steps using a conservative variant of Miller and Reif's tree-contraction technique.This research was supported in part by the Defense Advanced Research Projects Agency under Contract N00014-80-C-0622 and by the Office of Naval Research under Contract N00014-86-K-0593. Charles Leiserson is supported in part by an NSF Presidential Young Investigator Award with matching funds provided by AT&T Bell Laboratories and Xerox Corporation. Bruce Maggs is supported in part by an NSF Fellowship.     

A Multiphase Level Set Framework for Image Segmentation Using the Mumford and Shah Model

We propose a new multiphase level set framework for image segmentation using the Mumford and Shah model, for piecewise constant and piecewise smooth optimal approximations. The proposed method is also a generalization of an active contour model without edges based 2-phase segmentation, developed by the authors earlier in T. Chan and L. Vese (1999. In Scale-Space'99, M. Nilsen et al. (Eds.), LNCS, vol. 1682, pp. 141–151) and T. Chan and L. Vese (2001. IEEE-IP, 10(2):266–277). The multiphase level set formulation is new and of interest on its own: by construction, it automatically avoids the problems of vacuum and overlap; it needs only log n level set functions for n phases in the piecewise constant case; it can represent boundaries with complex topologies, including triple junctions; in the piecewise smooth case, only two level set functions formally suffice to represent any partition, based on The Four-Color Theorem. Finally, we validate the proposed models by numerical results for signal and image denoising and segmentation, implemented using the Osher and Sethian level set method.