Performance evaluation of algorithms for transitive closure

摘要

This paper presents the results of an experimental evaluation of the performance of three main algorithms for transitive closure: Seminaive, Smart and Blocked Warren. The algorithms have been implemented using a variety of join methods (block nested-loops and hash-join), disk-based and memory-based data structures and buffer replacement strategies. The algorithms were tested on several graphs, ranging from regular trees to random acyclic graphs to random general graphs. Contrary to what several previous studies have found, our experiments indicate that Seminaive is almost always superior to Smart. In most cases, Seminaive exhibited inferior performance to Warren, but surprisingly, there are some types of graphs where Blocked Warren generates more duplicates than Seminaive and is therefore slower. Finally, for the common case where a transitive closure query involves a selection, Seminaive can take advantage of the constants in the selection, whereas Blocked Warren and Smart cannot. Our experiments indicate that the percentage of the graph nodes that need to be selected for Blocked Warren to be superior to Seminaive is rather large (for all graphs tested, it must be greater than 13). This implies that for the majority of transitive closure queries with selection, Seminaive is the preferred strategy.