Output-optimal parallel algorithms for similarity joins

Hu, Xiao, Tao, Yufei and Yi, Ke (2017). Output-optimal parallel algorithms for similarity joins. In: International Conference on Management of Data, Chicago, IL, USA, (79-90). 14-19 May 2017. doi:10.1145/3034786.3056110

Author Hu, Xiao
Tao, Yufei
Yi, Ke
Title of paper Output-optimal parallel algorithms for similarity joins
Conference name International Conference on Management of Data
Conference location Chicago, IL, USA
Conference dates 14-19 May 2017
Series Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
Publisher Association for Computing Machinery
Publication Year 2017
Sub-type Fully published paper
DOI 10.1145/3034786.3056110
Open Access Status Not yet assessed
ISBN 9781450341981
Volume Part F127745
Start page 79
End page 90
Total pages 12
Chapter number 7
Total chapters 35
Language eng
Abstract/Summary Parallel join algorithms have received much attention in recent years, due to the rapid development of massively parallel systems such as MapReduce and Spark. In the database theory community, most efforts have been focused on studying worst-optimal algorithms. However, the worst-case optimality of these join algorithms relies on the hard instances having very large output sizes. In the case of a two-relation join, the hard instance is just a Cartesian product, with an output size that is quadratic in the input size. In practice, however, the output size is usually much smaller. One recent parallel join algorithm by Beame et al. [8] has achieved output-optimality, i.e., its cost is optimal in terms of both the input size and the output size, but their algorithm only works for a 2-relation equi-join, and has some imperfections. In this paper, we first improve their algorithm to true optimality. Then we design output-optimal algorithms for a large class of similarity joins. Finally, we present a lower bound, which essentially eliminates the possibility of having output-optimal algorithms for any join on more than two relations.
Keyword Output-sensitive algorithms
Parallel computation
Similarity joins
Q-Index Code E1
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Conference Paper
Sub-type: Fully published paper
Collections: HERDC Pre-Audit
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: Scopus Citation Count Cited 2 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Sun, 24 Dec 2017, 05:49:11 EST