15492987
Automatic Accurate Time-Bound Analysis for High-Level Languages
This paper describes a general approach for automatic and accurate time-bound analysis. The approach consists of transformations for building time-bound functions in the presence of partially known input structures, symbolic evaluation of the time-bound function based on input parameters, optimizations to make the overall analysis efficient as well as accurate, and measurements of primitive parameters, all at the source-language level. We have implemented this approach and performed a number of experiments for analyzing Scheme programs. The measured worst-case times are closely bounded by the calculated bounds.
15838270
Eliminating Dead Code on Recursive Data
This paper describes a general and powerful method for dead code analysis and elimination in the presence of recursive data constructions. We represent partially dead recursive data using liveness patterns based on general regular tree grammars extended with the notion of live and dead, and we formulate the analysis as computing liveness patterns at all program points based on program semantics. This analysis yields a most precise liveness pattern for the data at each program point, which is significantly more precise than results from previous methods. The analysis algorithm takes cubic time in terms of the size of the program in the worst case but is very efficient in practice, as shown by our prototype implementation. The analysis results are used to identify and eliminate dead code. The general framework for representing and analyzing properties of recursive data structures using general regular tree grammars applies to other analyses as well.
8840929
Optimized Live Heap Bound Analysis
This paper describes a general approach for optimized live heap space and live heap space-bound analyses for garbage-collected languages. The approach is based on program analysis and transformations and is fully automatic. In our experience, the space-bound analysis generally produces accurate (tight) upper bounds in the presence of partially known input structures. The optimization drastically improves the analysis efficiency. The analyses have been implemented and experimental results confirm their accuracy and efficiency.
37778003
Automatic Accurate Cost-Bound Analysis for High-Level Languages
This paper describes a language-based approach for automatic and accurate cost-bound analysis. The approach consists of transformations for building cost-bound functions in the presence of partially known input structures, symbolic evaluation of the cost-bound function based on input size parameters, and optimizations to make the overall analysis efficient as well as accurate, all at the source-language level. The calculated cost bounds are expressed in terms of primitive cost parameters. These parameters can be obtained based on the language implementation or can be measured conservatively or approximately, yielding accurate, conservative, or approximate time or space bounds. We have implemented this approach and performed a number of experiments for analyzing Scheme programs. The results helped confirm the accuracy of the analysis.
9019278
Querying Complex Graphs
This paper presents a powerful language for querying complex graphs and a method for generating efficient implementations that can answer queries with complexity guarantees. The graphs may have edge labels that may have parameters, and easily and naturally capture complex interrelated objects in object-oriented systems and XML data. The language is built on extended regular path expressions with variables and scoping, and can express queries more easily and clearly than previous query languages.The method for implementation first transforms queries into Datalog with limited extensions. It then extends a previous method to generate specialized algorithms and complexity formulas from Datalog with these extensions.
5528420
Automatic time-bound analysis for a higher-order language
Analysis of program running time is important for several applications, including reactive systems, interactive environments, compiler optimizations and performance evaluation. Automatic and efficient prediction of accurate time bounds is particularly important, and being able to do so for high-level languages is particularly desirable. This paper presents a general approach for automatic and accurate time-bound analysis for a functional high-level language, that combines methods and techniques studied in theory, languages, and systems. The approach consists of transformations for building time-bound functions in the presence of partially known input structures, symbolic evaluation of the time-bound function based on input parameters, optimizations to make the analysis efficient as well as accurate, and measurements of primitive parameters, all at the source-language level. To handle higher-order functions, special transformations are needed to build lambda expressions for computing running times, to optimize the construction of the time lambda expressions, and to optimize the symbolic evaluation. It took us several tries to obtain the simple and concise transformations for handling lambda expressions. We describe analysis and transformation algorithms and explain how they work. We have implemented this approach and performed a large number of experiments analyzing Scheme programs. The measured worst-case times are closely bounded by the calculated bounds. We describe our prototype system, ALPA, as well as the analysis and measurement results.
5651676
Segmentation Conditional Random Fields (SCRFs): A New Approach for Protein Fold Recognition
Protein fold recognition is an important step towards understanding protein three-dimensional structures and their functions. A conditional graphical model, i.e. segmentation conditional random fields (SCRFs), is proposed to solve the problem. In contrast to traditional graphical models such as hidden markov model (HMM), SCRFs follow a discriminative approach. It has the flexibility to include overlapping or long-range interaction features over the whole sequence, as well as global optimally solutions for the parameters. On the other hand, the segmentation setting in SCRFs makes its graphical structures intuitively similar to the protein 3-D structures and more importantly, provides a framework to model the long-range interactions directly. 
 
Our model is applied to predict the parallel β-helix fold, an important fold in bacterial infection of plants and binding of antigens. The cross-family validation shows that SCRFs not only can score all known β-helices higher than non β-helices in Protein Data Bank, but also demonstrate more success in locating each rung in the known β-helix proteins than BetaWrap, a state-of-the-art algorithm for predicting β-helix fold, and HMMER, a general motif detection algorithm based on HMM. Applying our prediction model to Uniprot database, we hypothesize previously unknown β-helices.
36759557
Geometrical analysis of two sets of 3D correspondence data patterns
Given two sets of image correspondence data, the analysis of the corresponding rigid body transformation that accurately describes the object's motion in 3D space is a fundamental problem in image understanding. While many methods have been put forward to analyse 3D transformations, such methods do not make use of the vector distance between feature points and angular information as constraints to analyse transformation parameters. Current methods and algorithms have also suffered from the problems of lack of efficiency, sensitivity to noise, and multiplicity of solutions. In this paper we present a novel geometrical analysis of rigid body transformations and a novel algorithm to calibrate transformation parameters based on image correspondence. The algorithm is validated through experimental calibration and a comparison is made with calibration implemented by the least squares method. We demonstrate that the proposed algorithm works well in the presence of noise and that its performance is in general superior to algorithms based on the least squares method.
10845590
Developing structural constraints for accurate registration of overlapping range images
Abstract Automatic image registration is an attractive and unresolved problem in the machine vision literature. This paper presents two novel structural constraints, namely proximity and closeness constraints, that improve both the accuracy and robustness of an existing motion consistency based algorithm (GICP) for automatic image registration. It also defines the conditions when such constraints are fired at specific points of the registration of two overlapping range images. The proximity constraint says that neighbouring points should be neighbouring before and after a rigid motion. The closeness constraint implements a local closest point search from the second image to the first image. While the GICP algorithm uses an exhaustive search for the closest points, in this paper, we employ the optimised k–d tree data structure to accelerate the closest point search. A large number of experiments based on real range images demonstrate that the combination of rigid motion constraints with these novel proximity and closeness constraints leads to a more accurate and robust evaluation of possible correspondences leading, in turn, to more accurate, robust and efficient automatic image registration results.
4427518
On the stability of rational, heterogeneous interdomain route selection
The recent discovery of instability caused by the interaction of local routing policies of multiple ASes has led to extensive research on the subject. However, previous studies analyze stability under a specific route selection algorithm. In this paper, instead of studying a specific route selection algorithm, we study a general class of route selection algorithms which we call rational route selection algorithms. We present a sufficient condition to guarantee routing convergence in a heterogeneous network where each AS runs any rational route selection algorithm. Applying our general results, we study the potential instability of a network where the preference of an AS depends on not only its egress routes to the destinations but also its inbound traffic patterns (i.e., the distribution of incoming traffic from its neighbors). We show that there exist networks which will have persistent route oscillations even when the ASes strictly follow the constraints imposed by business considerations, and adopt any rational route selection algorithms.
10859249
Making use of population information in evolutionary artificial neural networks
This paper is concerned with the simultaneous evolution of artificial neural network (ANN) architectures and weights. The current practice in evolving ANN's is to choose the best ANN in the last generation as the final result. This paper proposes a different approach to form the final result by combining all the individuals in the last generation in order to make best use of all the information contained in the whole population. This approach regards a population of ANN's as an ensemble and uses a combination method to integrate them. Although there has been some work on integrating ANN modules, little has been done in evolutionary learning to make best use of its population information. Four linear combination methods have been investigated in this paper to illustrate our ideas. Three real-world data sets have been used in our experimental studies, which show that the recursive least-square (RLS) algorithm always produces an integrated system that outperforms the best individual. The results confirm that a population contains more information than a single individual. Evolutionary learning should exploit such information to improve generalization of learned systems.