Optimal Joins
Distributed algorithms for evaluating join queries with formal optimality guarantees on their communication cost, for big data systems that partition data across cluster nodes.
Website: VUB research portal Funding: FWO Research Project Timeline: 2021–2024 PI: Bas Ketsman
Modern big data systems partition data across independently operating compute nodes, so that the dominating cost of their algorithms is communication: the amount of data exchanged and the number of synchronisation rounds between nodes. The relational join is a particularly challenging operator in this setting. This project (Optimal Join Algorithms for Modern Distributed Data Systems) studied the precise complexity of join queries in cluster settings, and developed algorithms that compute joins with formal optimality guarantees on their communication cost.