8380823
Term Matching on Parallel Computers
Term matching is an important problem that arises very often in term rewriting and in functional and equational programming. In this paper, we present a new parallel algorithm for the term-matching problem on the EREW (Exclusive Read Exclusive Write) model of parallel computation. Our algorithm assumes a string representation of the two terms as its input. The string representation is first transformed into two labeled ordered trees and term matching is then performed on these two trees. If n is the length of the input terms then for any constant ∈, (0<#x2208;≤1) our algorithm uses O(n1−∈) processors and takes O(nelog n) time. If e=0 the same algorithm will run in O(log2n) time. The only other known parallel algorithm for this problem is due to Dwork, Kanellakis and Stockmeyer that requires O(n2) processors and takes either O(log n) or O(log2n) time. However, their algorithm uses the stronger CREW (Concurrent Read Exclusive Write) model of parallel computation and assumes a DAG (Directed Acyclic Graph) representation of the two terms as its input. The techniques used in our algorithm are novel and have wide applicability.
42187803
Incremental Techniques for Efficient Normalization of Nonlinear Rewrite Systems
In [8] we described a nonlinear pattern-matching algorithm with the best known worst-case and optimal average-case time complexity. In this paper we first report on some experiments conducted on our algorithm. Based on these experiments we believe that our algorithm is useful in speeding up normalization of nonlinear rewrite systems even when it has a small number (≥5) of rewrite rules.
5663050
Term Matching on Parallel Computers
Term matching is an important problem that arises very often in term rewriting and in functional and equational programming. We present a new parallel algorithm for the term-matching problem on the EREW (exclusive read, exclusive write) model of parallel computation. Our algorithm assumes a string representation of the two terms as its input. The string representation is first transformed into two labeled ordered trees, and term matching is then performed on these two trees. If n is the length of the input terms, then for any constant ϵ (0 < ϵ ≤ 1) our algorithm uses O(n1-ϵ) processors and takes O(nϵlogn) time. If ϵ = 0, the same algorithm will run in O(log2 n) time. The only other known parallel algorithm for this problem, due to Dwork, Kanellakis, and Stockmeyer, requires O(n2) processors and takes either O(logn) or O(log2n) time. However, their algorithm uses the stronger CREW (concurrent read, exclusive write) model of parallel computation and assumes a DAG (directed acyclic graph) representation of the two terms as its input. On the CRCW (concurrent read, concurrent write) model our algorithm requires n processors and O(log n) time.
206085776
Parallel Tree Pattern Matching
Tree pattern matching is a fundamental operation that is used in a number of programming tasks such as code optimization in compilers, symbolic computation, automatic theorem proving and term rewriting. An important special case of this operation is linear tree pattern matching in which an instance of any variable in the pattern occurs at most once. In this paper we describe a new parallel algorithm for linear tree pattern matching using a parallel random access machine model.
10316561
Variable-depth trie index optimization: theory and experimental results
We develop an efficient approach to Trie index optimization. A Trie is a data structure used to index a file having a set of attributes as record identifiers. In the proposed methodology, a file is horizontally partitioned into subsets of records using a Trie index whose depth of indexing is allowed to vary. The retrieval of a record from the file proceeds by “stepping through” the index to identify a subset of records in the file in which a binary search is performed. This paper develops a taxonomy of optimization problems underlying variable-depth Trie index construction. All these problems are solvable in polynomial time, and their characteristics are studied. Exact algorithms and heuristics for their solution are presented. The algorithms are employed in CRES-an expert system for editing written narrative material, developed for the Department of the Navy. CRES uses several large-to-very-large dictionary files for which Trie indexes are constructed using these algorithms. Computational experience with CRES shows that search and retrieval using variable-depth Trie indexes can be as much as six times faster than pure binary search. The space requirements of the Tries are reasonable. The results show that the variable-depth Tries constructed according to the proposed algorithms are viable and efficient for indexing large-to-very-large files by attributes in practical applications.
42876448
Optimal Speedups for Parallel Pattern Matching in Trees
Tree pattern matching is a fundamental operation that is used in a number of programming tasks such as code optimization in compilers, symbolic computation, automatic theorem proving and term rewriting. An important special case of this operation is linear tree pattern matching in which an instance of any variable in the pattern occurs at most once. If n and m are the number of nodes in the subject and pattern tree respectively and if no restriction is placed on the structure of the trees, then the fastest known sequential algorithm for linear tree pattern matching requires O(nm) time in the worst case.
773323
Intelligent computer integrated manufacturing (I-CIM): Research perspectives
Abstract Manufacturing automation has progressed through various stages from simple data transfer to the intelligence-intensive systems. The future of CIM relies heavily on intelligence-intensive systems because manufacturing is no longer confined to one local site and manufacturing systems have become complex because of their global nature. In this article, the authors study the future manufacturing environment as a collaborative effort. The essential characteristics-the requirements for integration from a process and communication perspective-are identified as are steps in the process requiring further study. Finally, Intelligent-Computer Integrated Manufacturing (I-CIM) scenarios are presented for specific problems.
316216
The Distribution Problem with Carrier Service: A Dual Based Penalty Approach
The distribution problem with carrier service is an important optimization problem that often arises in vehicle routing. The problem arises in the distribution of commodities from a central facility to a set of geographically distributed locations. Each location has a certain demand, the distribution vehicle has a load capacity, and the entire operation should be completed within a certain time. An outside carrier is available for direct service of locations from the central facility. The problem is to determine a feasible tour for the company vehicle and the locations to be served by the outside carrier such that the total cost of the operations is minimized. We model this problem and develop a solution technique using valid inequalities. A key feature of the solution approach is that it can easily be extended to solve similar problems with any type and number of side constraints as encountered in the current model. The algorithm has been extensively tested and computational results for problems having u...
120648016
Theory of convex cones in multicriteria decision making
We develop the theory of convex polyhedral cones in the objective-function space of a multicriteria decision problem. The convex cones are obtained from the decision-maker's pairwise judgments of decision alternatives and are applicable to any quasiconcave utility function. Therefore, the cones can be used in any progressively articulated solution procedure that employs pairwise comparisons. The cones represent convex sets of solutions that are inferior to known solutions to a multicriteria problem. Therefore, these convex sets can be eliminated from consideration while solving the problem. We develop the underlying theory and a framework for representing knowledge about the decision-maker's preference structure using convex cones. This framework can be adopted in the interactive solution of any multicriteria problem after taking into account the characteristics of the problem and the solution procedure. Our computational experience with different multicriteria problems shows that this approach is both viable and efficient in solving practical problems of moderate size.
120676923
Preference Structure Representation Using Convex Cones in Multicriteria Integer Programming
A new efficient system of representing the decision-maker's preference structure in solving multicriteria integer programming problems is developed. The problem is solved by an interactive branch-and-bound method that employs the procedure of Zionts and Wallenius Zionts, S., J. Wallenius. 1983. An interactive multiple objective linear programming method for a class of underlying nonlinear utility functions. Management Sci.295. for multicriteria linear programming. The decision-maker's underlying utility function is assumed to be pseudoconcave, and his pairwise comparisons of decision alternatives are used to determine his preference structure in terms of certain convex cones in the objective function space and constraints on the weights on the objectives in the weight space. The two forms of preference structure representation are interrelated, and their underlying theory is developed. The primary objective of a representation scheme is exactness, and, in this respect, it is shown that the constraints on the weights are not adequate for representing nonlinear utility functions. On the other hand, the convex cones exactly represent any quasiconcave utility function and clearly avoid the approximations and inaccuracies in other utility assessment systems. Accordingly, an efficient ordered representation using convex cones is developed. An algorithmic framework for multicriteria integer programming that integrates the representation using convex cones with the branch-and-bound solution procedure is developed. Computational experience with bicriteria problems having up to 80 variables and 40 constraints is presented.
28568598
Cascade Graphs: Design, Analysis and Algorithms for Relational Joins
The focus of this work is on join optimization in relational database systems. The importance of join optimization is critically underscored by the high cost of relational joins and their frequent needs in traditional as well as emerging database applications. We demonstrate that the sequence in which the pages of the relations are accessed to process a join is a critical determinant of the join execution cost and an optimization of this sequence can lead to a significant improvement in performance over the traditional approaches. We initially develop three network structures to represent a join on two relations:page connectivity graph, cascade andblock tree cascade. A page connectivity graph is a bipartite representation of the set of connected pages in the two relations according to the join predicate. To reveal the structural properties of the join, the nodes of the bipartite graph are ordered into a set of levels, and the resulting isomorphic structure is termed acascade. From the cascade, a tree structure termed ablock tree cascade is derived by selectively grouping nodes at each level of the cascade intoblocks. We formulate the join as a tree traversal process, and accordingly develop efficient tree traversal algorithms. We develop a compact data structure to store the resulting access path, and provide a comprehensive analysis of the algorithms with detailed assessments of their performance. The performance evaluation demonstrates that the proposed approach can result in significant cost savings over the current join processing methods, for low to modest values of the join selectivity factor.