Parallel transitive closure computations using topological sort
| Title | Parallel transitive closure computations using topological sort |
| Publication Type | Conference Papers |
| Year of Publication | 1991 |
| Authors | Hua KA, Hannenhalli S |
| Conference Name | , Proceedings of the First International Conference on Parallel and Distributed Information Systems, 1991 |
| Date Published | 1991/12/04/6 |
| Publisher | IEEE |
| ISBN Number | 0-8186-2295-4 |
| Keywords | Computer 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 |
| DOI | 10.1109/PDIS.1991.183079 |