Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/24980
Title: | A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries | Authors: | KETSMAN, Bas Suciu, Dan |
Issue Date: | 2017 | Publisher: | ACM | Source: | Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, ACM,p. 417-428 | Abstract: | We study the optimal communication cost for computing a full conjunctive query Q over p distributed servers. Two prior results were known. First, for one-round algorithms over skew-free data the optimal communication cost per server is m/p^(1/tau*), where m is the size of the largest input relation, and tau* is the fractional vertex covering number of the query hypergraph. Second, for multi-round algorithms and unrestricted database instances, it was shown that any algorithm requires at least m/p^(1/rho*) communication cost per server, where rho* is the fractional edge covering number of the query hypergraph; but no matching algorithms were known for this case (except for two restricted queries: chains and cycles). In this paper we describe a multi-round algorithm that computes any query with load m/p^(1/rho*) per server, in the case when all input relations are binary. Thus, we prove this to be the optimal load for all queries over binary input relations. Our algorithm represents a non-trivial extension of previous algorithms for chains and cycles, and exploits some unique properties of graphs, which no longer hold for hyper-graphs. | Keywords: | Conjunctive queries; Multi-round; Worst-case optimal load | Document URI: | http://hdl.handle.net/1942/24980 | ISBN: | 9781450341981 | DOI: | 10.1145/3034786.3034788 | ISI #: | 000455480400033 | Rights: | (c) 2017 Copyright held by the owner/author(s). | Category: | C1 | Type: | Proceedings Paper |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
p417-ketsman.pdf Restricted Access | Published version | 707.42 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
19
checked on Sep 3, 2020
WEB OF SCIENCETM
Citations
14
checked on May 4, 2024
Page view(s)
102
checked on Sep 7, 2022
Download(s)
82
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.