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

Summary: Parallel transitive closure via double-hash on-disk clustering, avoiding extra I/O and keeping memory bounded. A shared-nothing cyclic execution achieves near-p-fold speedup with limited communication and no serialized transfers. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8147
Venue: VLDB
Year: 1990
Pagerank: 5.3766157e-05
Overall Rank: 8,775 | 39.80%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jean-Pierre Cheiney (École Nationale Supérieure des Télécommunications)
2. Christophe de Maindreville (INRIA)

BibTeX Citation

@article{cheiney_vldb90,
        title = {{A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering}},
        author = {Cheiney, Jean-Pierre and de Maindreville, Christophe},
        journal = {PVLDB},
        series = {{VLDB} '90},
        pages = {347},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
13,065	Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB	1993	VLDB	5.093636e-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
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00083340894
52	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00041107291
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
242	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023604323
282	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.0002242162
1,114	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00012118382
1,330	Efficient Transitive Closure Algorithms	1988	VLDB	0.00011140171

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,011	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
2	282	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD
3	1,259	On the Computation of the Transitive Closure of Relational Operators	1986	VLDB
4	7,438	A Generalized Transitive Closure for Relational Queries	1988	PODS
5	3,491	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD
6	1,114	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB
7	5,341	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB
8	1,330	Efficient Transitive Closure Algorithms	1988	VLDB
9	13,065	Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB	1993	VLDB
10	1,086	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB