Cartesian Operations on Distributed Datasets Using Virtual Partitioning
Michael A. Phinney, Sean Lander, Matt Spencer, Chi‐Ren Shyu · 2016
The Cartesian product is a technique used in a wide range of algorithms. Performing a Cartesian product on a distributed dataset poses a variety of challenges. The process requires enormous amounts of data to be shuffled between nodes, and the computation effectively squares the size of the input data. As a result, for large scale analyses, this sort of pairwise operation is likely to be the bottleneck of any computational pipeline. Existing approaches provide solutions, however, quickly incur large delays as the size of the input dataset increases. In this paper, we introduce the Cartesian Scheduler, a generalized mechanism that allows Cartesian products to be performed efficiently in big data ecosystems such as an Apache Spark cluster. We present a few experiments to highlight the efficiency and flexibility of our approach and compare our proposed method with the current state-of-the-art Cartesian operations.