Semi-Join Algorithms For Multiprocessor Systems

Summary: Proposes semi-join algorithms for multiprocessor DB machines, with an architecture model that includes I/O, CPU, and inter-processor messaging costs. Compares two equi-semi-join variants and one inequij-semi-join, showing semi-join methods cut communication and scale linearly with operand size and processor count. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2253
Venue: SIGMOD
Year: 1982
Pagerank: 5.5306397e-05
Overall Rank: 7,857 | 46.10%
DOI: 10.1145/582353.582396

Incoming Non-self Citations Over Time

Authors

1. Patrick Valduriez (INRIA)

BibTeX Citation

@inproceedings{valduriez_sigmod82,
        title = {{SEMI-JOIN ALGORITHMS FOR MULTIPROCESSOR SYSTEMS}},
        author = {Valduriez, Patrick},
        series = {{SIGMOD} '82},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/582353.582396},
        url = {https://dl.acm.org/doi/10.1145/582353.582396},
        year = {1982}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,352	Range Nesting: A Fast Method To Evaluate Quantified Queries	1983	SIGMOD	6.2528892e-05
8,721	Accelerate Distributed Joins with Predicate Transfer	2025	SIGMOD	5.3772617e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,510	A Methodology For Interpreting Tree Queries Into Optimal Semi-Join Expressions	1980	SIGMOD	0.00010539169
2,170	Query Execution in DIRECT	1979	SIGMOD	9.042724e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	152	Multiprocessor Hash-Based Join Algorithms	1985	VLDB
2	2,104	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
3	242	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD
4	1,479	Computing Joins Of Relations	1975	SIGMOD
5	4,668	Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor	1991	VLDB
6	9,987	Optimal Semijoin Schedules For Query Processing In Local Distributed Database Systems	1981	SIGMOD
7	1,772	A Heuristic Approach to Distributed Query Processing	1982	VLDB
8	5,069	Query Processing For Distributed Databases Using Generalized Semi-Joins	1982	SIGMOD
9	1,651	On the Design of a Query Processing Strategy in a Distributed Database Environment	1983	SIGMOD
10	13,231	Using Semiouterjoins to Process Queries in Multidatabase Systems	1984	PODS