13883054
Dynamic Programming via Static Incrementalization
Dynamic programming is an important algorithm design technique. It is used for solving problems whose solutions involve recursively solving subproblems that share subsubproblems. While a straightforward recursive program solves common subsubproblems repeatedly and often takes exponential time, a dynamic programming algorithm solves every subsubproblem just once, saves the result, reuses it when the subsubproblem is encountered again, and takes polynomial time. This paper describes a systematic method for transforming programs written as straightforward recursions into programs that use dynamic programming. The method extends the original program to cache all possibly computed values, incrementalizes the extended program with respect to an input increment to use and maintain all cached results, prunes out cached results that are not used in the incremental computation, and uses the resulting incremental program to form an optimized new program. Incrementalization statically exploits semantics of both control structures and data structures and maintains as invariants equalities characterizing cached results. The principle underlying incrementalization is general for achieving drastic program speedups. Compared with previous methods that perform memoization or tabulation, the method based on incrementalization is more powerful and systematic. It has been implemented and applied to numerous problems and succeeded on all of them.
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.
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.
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.
15516376
Supervised rank aggregation
This paper is concerned with rank aggregation, the task of combining the ranking results of individual rankers at meta-search. Previously, rank aggregation was performed mainly by means of unsupervised learning. To further enhance ranking accuracies, we propose employing supervised learning to perform the task, using labeled data. We refer to the approach as Supervised Rank Aggregation. We set up a general framework for conducting Supervised Rank Aggregation, in which learning is formalized an optimization which minimizes disagreements between ranking results and the labeled data. As case study, we focus on Markov Chain based rank aggregation in this paper. The optimization for Markov Chain based methods is not a convex optimization problem, however, and thus is hard to solve. We prove that we can transform the optimization problem into that of Semidefinite Programming and solve it efficiently. Experimental results on meta-searches show that Supervised Rank Aggregation can significantly outperform existing unsupervised methods.
18353926
Inverse validation for accurate range image registration with structured data
Automatic range image registration is a fundamental yet extremely difficult problem in machine vision. In this paper, we extend a promising registration algorithm, the geometric iterative closest point (GICP), for structured image data. The extended algorithm is based on a relaxation method combining the motion estimation results from the possible correspondences established by the GICP algorithm and those that are further evaluated by an inverse validation procedure. A comparative study based on real images has shown that the extended algorithm is more accurate and robust than the original algorithm.
1369726
Adaptive Data Fusion for Energy Efficient Routing in Wireless Sensor Networks
While in-network data fusion can reduce data redundancy and, hence, curtail network load, the fusion process itself may introduce significant energy consumption for emerging wireless sensor networks with vectorial data and/or security requirements. Therefore, fusion-driven routing protocols for sensor networks cannot optimize over communication cost only - fusion cost must also be accounted for. In our prior work, while a randomized algorithm termed MFST is devised toward this end, it assumes that fusion shall be performed at any intersection node whenever data streams encounter. In this paper, we design a novel routing algorithm, called adaptive fusion Steiner tree (AFST), for energy efficient data gathering. Not only does AFST jointly optimize over the costs for both data transmission and fusion, but also AFST evaluates the benefit and cost of data fusion along information routes and adaptively adjusts whether fusion shall be performed at a particular node. Analytically and experimentally, we show that AFST achieves better performance than existing algorithms, including SLT, SPT, and MFST
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.
7269331
Quadric Surface Extraction by Variational Shape Approximation
Based on Lloyd iteration, we present a variational method for extracting general quadric surfaces from a 3D mesh surface. This work extends the previous variational methods that extract only planes or special types of quadrics, i.e., spheres and circular cylinders. Instead of using the exact L2 error metric, we use a new approximate L2 error metric to make our method more efficient for computing with general quadrics. Furthermore, a method based on graph cut is proposed to smooth irregular boundary curves between segmented regions, which greatly improves the final results.