Carleton University
Technical Report TR-01-01
March 2001
Coarse Grained Parallel Fixed-Parameter Tractable Algorithms
Abstract
FPT algorithms have been successful in allowing to solve NP-complete problems for certain problem instances of practical importance. In this paper we show how to enhance this approach through the addition of parallelism, thereby allowing even larger problem instances to be solved in practice. More precisely, we demonstrate the potential of parallelism when applied to the bounded tree search phase of FPT algorithms. We introduce a new definition of practical parallel FPT algorithms which is based on the speedup obtained for the entire algorithm and addresses shortcomings with previous definitions PNC and FPP) that were not efficient in practice. We apply our methodology to the k Vertex Cover problem which has important applications, e.g. in multiple sequence alignments for computational biochemistry. We have implemented our parallel k Vertex Cover algorithm in C/MPI and tested it on a network of 10 Sun SPARC workstations. This is the first experimental examination of parallel FPT techniques. In our experiments, we obtain excellent speedup results. Not only do we achieve a speedup of p in most cases, many cases even exhibit a super linear speedup. The latter result implies that our parallel methods, when simulated on a single processor, also yield a significant improvement over existing sequential methods.Current database systems utilize histograms to approximate frequency distributions of attribute values of relations. These are used to efficiently estimate query result sizes and access plan costs. Even though they have been in use for nearly two decades, there has been no significant mathematical techniques (other than those used in statistics for traditional histogram approximations) to study them. In this paper, we introduce a new histogram-like approximation strategy, called the Rectangular Attribute Cardinality Map (R-ACM), that aims to approximate the density of the underlying attribute values using the philosophies of numerical integration. In this new histogram-like approximation method, the density function within a given sector is approximated by a rectangular cell, where the height of the cell is ob- tained so as to guarantee that the actual probability density differs from the approxi- mated one by a maximum of a user-specified tolerance. Furthermore, unlike the two traditional histogram types, namely equi-width and equi-depth, the R-ACM is neither equi-width nor equi-depth. Analytically, we show that for the R-ACM, the distribu- tion of an attribute value within the sector is Binomially distributed. This permits us to derive worst-case and average-case results for the estimation errors of the probabil- ity mass itself. Our theoretical results, which include a rigorous maximum likelihood and expected-case analyses, and an extensive set of experiments demonstrate that the R-ACM scheme (which is essentially histogram-like) is much more accurate than the traditional histograms for query result size estimation. Due to its high accuracy and low construction costs, we hope that it could become an invaluable tool for query optimization in the future database systems.