Worst-Case Optimal Algorithms for Parallel Query Processing

339 views · Published 25 February 2016 · 53:23 · Indexed 25 October 2026

Channel: Institut Henri Poincaré · 2016 · Science & Technology

Watch on YouTube

By Paris Koutris (University of Wisconsin) 
Abstract: We study the communication complexity for the problem of computing a conjunctive query on a large database in a massively parallel setting. In contrast to previous work, where upper and lower bounds on the communication were specified for particular structures of data, in this work we focus on worst-case analysis of the communication cost. We also show a surprising connection to the external memory model, which allows us to translate parallel algorithms to external memory algorithms. This technique allows us to recover several recent results on the I/O complexity for computing join queries, and also obtain optimal algorithms for other classes of queries.

More from this channel