A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering

Summary: Parallel transitive-closure algorithm using double-hash-based on-disk clustering; memory-efficient with no extra I/O. Time reduced by a factor of p on p processors with cyclic communication in a shared-nothing setting; benefits demonstrated. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7957
Venue: VLDB
Year: 1990
Pagerank: 4.4893996e-05
Overall Rank: 8,569 | 40.45%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jean-Pierre Cheiney
2. Christophe de Maindreville

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,881	Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB	1993	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
9	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.001426258
21	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00086104592
79	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00056010993
230	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00032145125
255	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030342925
815	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.0001629507
885	Efficient Transitive Closure Algorithms	1988	VLDB	0.00015565543

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,599	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD	8.4655075e-05
255	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030342925
1,078	On The Computation Of The Transitive Closure Of Relational Operators	1986	VLDB	0.00014223265
7,182	A Generalized Transitive Closure for Relational Queries	1988	PODS	4.802834e-05
2,679	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	8.3223476e-05
815	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.0001629507
4,855	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB	5.8698466e-05
885	Efficient Transitive Closure Algorithms	1988	VLDB	0.00015565543
12,881	Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB	1993	VLDB	4.1905499e-05
792	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB	0.00016580866