Algorithm Engineering and Experiments

Some of the most widely used constructive heuristics for the Steiner Problem in Graphs are based on algorithms for the Minimum Spanning Tree problem. In this paper, we examine efficient implementations of heuristics based on the classic algorithms by Prim, Kruskal, and Borůvka. An extensive experimental study indicates that the theoretical worst-case complexity of the algorithms give little information about their behavior in practice. Careful implementation improves average computation times not only significantly, but asymptotically. Running times for our implementations are within a small constant factor from that of Prim’s algorithm for the Minimum Spanning Tree problem, suggesting that there is little room for improvement.

Leading algorithms for Boolean satisfiability (SAT) are based on either a depth-first tree traversal of the search space (the DLL procedure [6]) or resolution (the DP procedure [7]). In this work we introduce a variant of Breadth-First Search (BFS) based on the ability of Zero-Suppressed Binary Decision Diagrams (ZDDs) to compactly represent sparse or structured collections of subsets. While a BFS may require an exponential amount of memory, our new algorithm performs BFS directly with an implicit representation and achieves unconventional reductions in the search space.

We empirically evaluate our implementation on classical SAT instances difficult for DLL/DP solvers. Our main result is the empirical Θ(n ⁴) runtime for hole-n instances, on which DLL solvers require exponential time.

In many fields of application, shortest path finding problems in very large graphs arise. Scenarios where large numbers of on-line queries for shortest paths have to be processed in real-time appear for example in traffic information systems. In such systems, the techniques considered to speed up the shortest path computation are usually based on precomputed information. One approach proposed often in this context is a space reduction, where precomputed shortest paths are replaced by single edges with weight equal to the length of the corresponding shortest path. In this paper, we give a first systematic experimental study of such a space reduction approach. We introduce the concept of multi-level graph decomposition. For one specific application scenario from the field of timetable information in public transport, we perform a detailed analysis and experimental evaluation of shortest path computations based on multi-level graph decomposition.

We empirically compare the local ratio algorithm for the profit maximization version of the dynamic storage allocation problem against various greedy algorithms. Our main conclusion is that, at least on our input distributions, the local ratio algorithms performed worse on average than the more naive greedy algorithms.

Caching and prefetching have often been studied as separate tools for enhancing the access to the World Wide Web. The goal of this work is to propose integrated Caching and Prefetching Algorithms for improving the performances of web navigation. We propose a new prefetching algorithm that uses a limited form of user cooperation to establish which documents to prefetch in the local cache at the client side. We show that our prefetching technique is highly beneficial only if integrated with a suitable caching algorithm. We consider two caching algorithms, Greedy-Dual-Size [6,17] and Least Recently Used, and demonstrate on trace driven simulation that Greedy-Dual-Size with prefetching outperforms both LRU with prefetching and a set of other popular caching algorithms.

Intuitively, the treewidth of a graph G measures how close G is to being a tree. The lower the treewidth, the faster we can solve various optimization problems on G, by dynamic programming along the tree structure. In the paper M.Thorup, All Structured Programs have Small Tree-Width and Good Register Allocation [8] it is shown that the control-flow graph of any goto-free C program is at most 6. This result opened for the possibility of applying the dynamic programming bounded treewidth algorithms to various compiler optimization tasks. In this paper we explore this possibility, in particular for Java programs. We first show that even if Java does not have a goto, the labelled break and continue statements are in a sense equally bad, and can be used to construct Java programs that are arbitrarily hard to understand and optimize.

For Java programs lacking these labelled constructs Thorup’s result for C still holds, and in the second part of the paper we analyze the treewidth of label-free Java programs empirically. We do this by means of a parser that computes a tree-decomposition of the control-flow graph of a given Java program. We report on experiments running the parser on several of the Java API packages, and the results tell us that on average the treewidth of the control-flow graph of these Java programs is no more than 2.7. This is the first empirical test of Thorup’s result, and it confirms our suspicion that the upper bounds of treewidth 6, 5 and 4 are rarely met in practice, boding well for the application of treewidth to compiler optimization.

A graph separator is a set of vertices or edges whose removal divides an input graph into components of bounded size. This paper describes new algorithms for computing separators in planar graphs as well as techniques that can be used to speed up their implementation and improve the partition quality. In particular, we consider planar graphs with costs and weights on the vertices, where weights are used to estimate the sizes of the components and costs are used to estimate the size of the separator. We show that one can find a small separator that divides the graph into components of bounded size. We describe implementations of the partitioning algorithms and discuss results of our experiments.

We describe two improvements to a previous implementation of out-of-core columnsort, in which data reside on multiple disks. The first improvement replaces asynchronous I/O and communication calls by synchronous calls within a threaded framework. Experimental runs show that this improvement reduces the running time to approximately half of the running time of the previous implementation. The second improvement uses algorithmic and engineering techniques to reduce the number of passes over the data from four to three. Experimental evidence shows that this improvement yields modest performance gains. We expect that the performance gain of this second improvement increases when the relative speed of processing and communication increases with respect to disk I/O speeds. Thus, as processing and communication become faster relative to I/O, this second improvement may yield bettor results than it currently does.

Topological sweep can contribute to efficient implementations of various algorithms for data analysis. Real data, however, has degeneracies. The modification of the topological sweep algorithm presented here handles degenerate cases such as parallel or multiply concurrent lines without requiring numerical perturbations to achieve general position. Our method maintains the O(n ²) and O(n) time and space complexities of the original algorithm, and is robust and easy to implement. We present experimental results.

This paper describes two simple modification of K-means and related algorithms for clustering, that improve the running time without changing the output. The two resulting algorithms are called Compare-means and Sort-means. The time for an iteration of K-means is reduced from O(ndk), where n is the number of data points, k the number of clusters and d the dimension, to O(ndγ + k ² d + k ² log k) for Sort-means. Here γ ≤ k is the average over all points p of the number of means that are no more than twice as far as p is from the mean p was assigned to in the previous iteration. Compare-means performs a similar number of distance calculations as Sort-means, and is faster when the number of means is very large. Both modifications are extremely simple, and could easily be added to existing clustering implementations.

We investigate the empirical performance of the algorithms on three datasets drawn from practical applications. As a primary test case, we use the Isodata variant of K-means on a sample of 2.3 million 6-dimensional points drawn from a Landsat-7 satellite image. For this dataset, γ quickly drops to less than log₂ k, and the running time decreases accordingly. For example, a run with k = 100 drops from an hour and a half to sixteen minutes for Compare-means and six and a half minutes for Sort-means. Further experiments show similar improvements on datasets derived from a forestry application and from the analysis of BGP updates in an IP network.

We present a new technique called STAR-tree, based on R*-tree, for indexing a set of moving points so that various queries, including range queries, time-slice queries, and nearest-neighbor queries, can be answered efficiently. A novel feature of the index is that it is self-adjusting in the sense that it re-organizes itself locally whenever its query performance deteriorates. The index provides tradeoffs between storage and query performance and between time spent in updating the index and in answering queries. We present detailed performance studies and compare our methods with the existing ones under a varying type of data sets and queries. Our experiments show that the index proposed here performs considerably better than the previously known ones.

The standard Tree Selection Sort is an efficient sorting algorithm but requires extra storage for n-1 pointers and n items. The goal of this paper is to not only reduce the extra storage of Tree Selection Sort to n bits, but also keep the number of comparisons at nlogn+O(n). The improved algorithm makes at most 3n data movements. The empirical results show that the improved algorithm is efficient. In some cases, say moving one item requires at least 3 assignment operations, the algorithm is the fastest on average among known fast algorithms.