Near-Optimal Distributed Band-Joins through Recursive Partitioning.

Area of Science:

• Computer Science
• Database Systems
• Distributed Computing

Background:

• Distributed systems require efficient data partitioning for tasks like band-joins.
• Balancing maximum load per worker and input duplication is a key challenge in distributed data processing.
• Existing methods for band-join partitioning face high optimization costs or restricted partitioning strategies.

Purpose of the Study:

• To develop a novel approach for optimizing running-time performance of band-joins in distributed systems.
• To resolve the tension between maximum load per worker and input duplication.
• To improve upon previous methods in terms of optimization cost and join performance.

Main Methods:

• Recursive partitioning of the join-attribute space.
• Utilizing an appropriate split scoring measure for partitioning.
• Evaluating the method for one-dimensional and multi-attribute band-joins.

Main Results:

• The recursive partitioning method achieves low optimization cost and low join cost.
• The approach is effective for both one-dimensional and multi-attribute band-joins.
• Experimental results show partitionings within 10% of the lower bound for load and duplication.

Conclusions:

• Recursive partitioning of the join-attribute space is an effective strategy for optimizing band-joins.
• This method offers significant improvements over previous work in distributed systems.
• The approach successfully balances load and duplication, leading to enhanced join performance.