## Line Graphs: Average Running Time vs. Number of Buckets (Tesla K40c, ECC Off)
### Overview
Two line graphs compare the average running time (ms) of four algorithms (BMS, Binomial, RB-Sort, Uniform) across varying numbers of buckets (m) for two scenarios: (a) Key-only and (b) Key-value. Both graphs show exponential increases in running time as the number of buckets grows, with distinct performance patterns between algorithms.
### Components/Axes
- **X-axis**: Number of buckets (m), logarithmic scale (1, 2, 4, 8, 16, 32, 64, 128, 256).
- **Y-axis**: Average running time (ms), linear scale (0–18 ms for Key-value, 0–14 ms for Key-only).
- **Legends**: Positioned at the top-right of each graph, with:
- **BMS**: Red circles (●)
- **Binomial**: Black solid line (—)
- **RB-Sort**: Blue triangles (▲)
- **Uniform**: Dotted line (···)
- **Titles**:
- (a) "key-only: Tesla K40c (ECC off)"
- (b) "key-value: Tesla K40c (ECC off)"
### Detailed Analysis
#### Graph (a): Key-only
- **BMS (●)**:
- Starts at ~3.5 ms (1 bucket), rises sharply after 128 buckets to ~12 ms (256 buckets).
- Intermediate values: ~4 ms (2 buckets), ~5 ms (4 buckets), ~6.5 ms (32 buckets).
- **Binomial (—)**:
- Flat at ~5 ms until 64 buckets, then jumps to ~9 ms (128 buckets), plateaus at ~9 ms (256 buckets).
- **RB-Sort (▲)**:
- Stable at ~5 ms until 64 buckets, then rises to ~9 ms (128 buckets), peaks at ~10 ms (256 buckets).
- **Uniform (···)**:
- Gradual increase from ~3.5 ms (1 bucket) to ~11 ms (256 buckets), with ~7 ms at 64 buckets.
#### Graph (b): Key-value
- **BMS (●)**:
- Starts at ~4 ms (1 bucket), rises sharply after 128 buckets to ~16 ms (256 buckets).
- Intermediate values: ~5 ms (2 buckets), ~6 ms (4 buckets), ~7.5 ms (32 buckets).
- **Binomial (—)**:
- Flat at ~5 ms until 64 buckets, then jumps to ~12 ms (128 buckets), plateaus at ~12 ms (256 buckets).
- **RB-Sort (▲)**:
- Stable at ~11 ms until 64 buckets, then rises to ~14 ms (128 buckets), peaks at ~16 ms (256 buckets).
- **Uniform (···)**:
- Gradual increase from ~4 ms (1 bucket) to ~15 ms (256 buckets), with ~8 ms at 64 buckets.
### Key Observations
1. **Exponential Scaling**: All algorithms show increased running time with more buckets, but BMS and RB-Sort exhibit steeper growth.
2. **Algorithm Performance**:
- **BMS**: Worst performance in both scenarios, especially at 256 buckets (~12 ms Key-only, ~16 ms Key-value).
- **RB-Sort**: Moderate performance, outperforming BMS but trailing Binomial/Uniform in Key-only.
- **Binomial/Uniform**: More stable, with Binomial showing minimal growth in Key-only but significant increases in Key-value.
3. **Threshold Behavior**: Sharp performance drops occur after 128 buckets for BMS and RB-Sort in both scenarios.
### Interpretation
The data suggests that the number of buckets critically impacts algorithm efficiency, with BMS and RB-Sort degrading rapidly as buckets exceed 128. Binomial and Uniform algorithms scale better but still face performance penalties in the Key-value scenario. The Key-value workload is consistently more demanding, likely due to additional data processing requirements. These trends highlight trade-offs between algorithm design and workload complexity, with implications for optimizing distributed systems or databases handling large-scale data partitioning.
