44572205
Strengthening invariants for efficient computation
Abstract This paper presents program analyses and transformations for strengthening invariants for the purpose of efficient computation. Finding the stronger invariants corresponds to discovering a general class of auxiliary information for any incremental computation problem. Combining the techniques with previous techniques for caching intermediate results, we obtain a systematic approach that transforms non-incremental programs into efficient incremental programs that use and maintain useful auxiliary information as well as useful intermediate results. The use of auxiliary information allows us to achieve a greater degree of incrementality than otherwise possible. Applications of the approach include strength reduction in optimizing compilers and finite differencing in transformational programming.
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.
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.
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.
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.
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.
619505
Semi-Supervised Learning of Attribute-Value Pairs from Product Descriptions
We describe an approach to extract attribute-value pairs from product descriptions. This allows us to represent products as sets of such attribute-value pairs to augment product databases. Such a representation is useful for a variety of tasks where treating a product as a set of attribute-value pairs is more useful than as an atomic entity. Examples of such applications include product recommendations, product comparison, and demand forecasting. We formulate the extraction as a classification problem and use a semi-supervised algorithm (co-EM) along with (Naive Bayes). The extraction system requires very little initial user supervision: using unlabeled data, we automatically extract an initial seed list that serves as training data for the supervised and semi-supervised classification algorithms. Finally, the extracted attributes and values are linked to form pairs using dependency information and co-location scores. We present promising results on product descriptions in two categories of sporting goods.
13965365
Distributed caching and adaptive search in multilayer P2P networks
To improve the scalability of Gnutella-like unstructured peer-to-peer (P2P) networks, a uniform index caching (UIC) mechanism was suggested in some earlier work. In UIC, query results are cached in all peers along the inverse query path such that the same query of other peers can be replied from their nearby-cached results. However, our experiments show that the UIC method causes a large amount of duplicated and unnecessary caching of items among neighboring peers. Aiming at improving the search efficiency, we propose a distributed caching mechanism, which distributes the cache results among neighboring peers. Furthermore, based on the distributed caching mechanism, an adaptive search approach is built which selectively forwards the query to the peers with a high probability of providing the desired cache results. All the enhancements above are defined in a protocol called distributed caching and adaptive search (DiCAS). In the DiCAS enhanced Gnutella network, all the peers are logically divided into multiple layers, with the character that all the peers in the same layer have the same group ID. The query flooding is restricted in one layer with the matched group ID. Our simulation study shows that, with the help of the index caching and search space division, the DiCAS protocol can significantly reduce the network search traffic in unstructured P2P systems without degrading query success rate.
2056912
Performance and Scalability Measurement of COTS EJB Technology
Enterprise Java Bean (EJB) is the core technology of J2EE platform to provide the foundation for scalable enterprise applications. About 30 product vendors provide implementations of the J2EE/EJB specification. As each of these products is designed and implemented differently, they show radically different performance profiles. To complicate this technology space, product vendors of J2EE products typically provide different infrastructure options and tuning techniques to address the requirements of performance and scalability. Therefore it is essential for developers to understand the performance and scalability issues of COTS EJB technologies so that the system can meet the performance requirements. In this paper, we investigate an approach to measure the performance and scalability of COTS EJB technology based on its architecture and technology analysis. A benchmark application is developed and tested to measure the system's performance as both the client load and component infrastructure are scaled up. The empirical results are presented and analyzed to evaluate the performance and scalability of the EJB technology under study.
8217950
Evolutionary ensembles with negative correlation learning
Based on negative correlation learning and evolutionary learning, this paper presents evolutionary ensembles with negative correlation learning (EENCL) to address the issues of automatic determination of the number of individual neural networks (NNs) in an ensemble and the exploitation of the interaction between individual NN design and combination. The idea of EENCL is to encourage different individual NNs in the ensemble to learn different parts or aspects of the training data so that the ensemble can learn better the entire training data. The cooperation and specialization among different individual NNs are considered during the individual NN design. This provides an opportunity for different NNs to interact with each other and to specialize. Experiments on two real-world problems demonstrate that EENCL can produce NN ensembles with good generalization ability.
1850975
Using classic problems to teach Java framework design
Abstract All programmers should understand the concept of software families and know the techniques for constructing them. This paper suggests that classic problems, such as well-known algorithms and data structures, are good sources for examples to use in a study of software family design. The paper describes two case studies that can be used to introduce students in a Java software design course to the construction of software families using software frameworks. The first is the family of programs that use the well-known divide and conquer algorithmic strategy. The second is the family of programs that carry out traversals of binary trees.