Parallel transitive closure computations using topological sort

TitleParallel transitive closure computations using topological sort
Publication TypeConference Proceedings
Year of Conference1991
AuthorsHua K.A, Hannenhalli S
Conference NameProceedings of the First International Conference on Parallel and Distributed Information Systems, 1991
Date Published1991
PublisherIEEE
ISBN Number0-8186-2295-4
KeywordsComputer science, Concurrent computing, data partitioning, Database systems, database theory, deductive databases, File systems, horizontal partitioning, joins, local data fragments, message passing multiprocessor system, Multiprocessing systems, Parallel algorithms, PARALLEL PROCESSING, parallel programming, parallel transitive closure, processing nodes, relation tuples, Relational databases, sorting, topological sort
Abstract

Deals with parallel transitive closure computations. The sort-based approaches introduced sorts the tuples of the relation into topological order, and the sorted relation is then horizontally partitioned and distributed across several processing nodes of a message passing multiprocessor system. This data partitioning strategy allows the transitive closure computation of the local data fragments to be computed in parallel with no interprocessor communication. The construction of the final result then requires only a small number of joins. Extensive analytical results are included in the paper as well. They show that the proposed techniques leads to a speedup that is essentially linear with the number of processors. Its performance is significantly better than the recently published hashless parallel algorithm