Parallel Evaluation of Multi-Semi-Joins

Summary: Introduces a multi-semi-join MapReduce operator for efficiently evaluating SGF queries, including disjunction and negation, in a single job. Parallel plans jointly optimize total and wall-clock time via effective greedy approximations, outperforming Pig and Hive. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 11550
Venue: VLDB
Year: 2016
Pagerank: 5.093636e-05
Overall Rank: 12,082 | 17.11%
DOI: 10.14778/2977797.2977802

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Jonny Daenen (Hasselt University)
2. Frank Neven (Hasselt University)
3. Tony Tan (National Taiwan University)
4. Stijn Vansummeren (Universite Libre de Bruxelles)

BibTeX Citation

@article{daenen_vldb16,
        title = {{Parallel Evaluation of Multi-Semi-Joins}},
        author = {Daenen, Jonny and Neven, Frank and Tan, Tony and Vansummeren, Stijn},
        journal = {PVLDB},
        series = {{VLDB} '16},
        volume = {9},
        number = {10},
        pages = {732--743},
        doi = {10.14778/2977797.2977802},
        url = {https://doi.org/10.14778/2977797.2977802},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
6	Pig Latin: A Not-So-Foreign Language for Data Processing	2008	SIGMOD	0.0010686205
290	An Overview of Query Optimization in Relational Systems	1998	PODS	0.0002227038
425	Shark: SQL and Rich Analytics at Scale	2013	SIGMOD	0.00018704491
769	A Comparison of Join Algorithms for Log Processing in MapReduce	2010	SIGMOD	0.00014166872
803	MRShare: Sharing Across Multiple Queries in MapReduce	2010	VLDB	0.00013899943
843	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00013666161
954	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012997301
1,207	Communication Steps for Parallel Query Processing	2013	PODS	0.00011663155
1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011166426
1,448	Skew in Parallel Query Processing	2014	PODS	0.00010758872
1,514	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00010527649
2,539	Minimal MapReduce Algorithms	2013	SIGMOD	8.4526595e-05
2,892	Scalable and Adaptive Online Joins	2014	VLDB	7.9852178e-05
3,163	Multi-Query Optimization in MapReduce Framework	2014	VLDB	7.6784171e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,515	Revisiting Pipelined Parallelism in Multi-Join Query Processing	2005	VLDB
2	2,887	Efficient Multi-way Theta-Join Processing Using MapReduce	2012	VLDB
3	72	Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters	2007	SIGMOD
4	8,894	Distributed Evaluation of Top-k Temporal Joins	2016	SIGMOD
5	3,163	Multi-Query Optimization in MapReduce Framework	2014	VLDB
6	1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
7	12,001	Runtime Optimization of Join Location in Parallel Data Management Systems	2017	VLDB
8	7,143	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS
9	954	Parallel Evaluation of Conjunctive Queries	2011	PODS
10	356	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD