MR-DIS: Scaling Democratic Instance Selection to Big Data with Spark

Executive Summary

TL;DR: MR-DIS is a parallelized version of the Democratic Instance Selection (DIS) algorithm designed for the Apache Spark environment. By utilizing a "voting" mechanism and MapReduce architecture, it reduces massive datasets to a manageable size with linear complexity—effectively solving the bottleneck where traditional preprocessing fails on big data.

Background: Within the academic landscape of data mining, instance selection is crucial for faster learning. However, most algorithms are too slow for millions of rows. MR-DIS positions itself as a scalable SOTA (State-of-The-Art) solution that bridges the gap between classic data reduction and modern distributed computing.

The Scaling Bottleneck: Why $O(n^2)$ is the Enemy

In the era of "Big Data," volume is a double-edged sword. While more data usually leads to better models, the computational cost of processing it grows exponentially for many algorithms. Most instance selection methods depend on pairwise comparisons of instances (to find neighbors or calculate distances), leading to quadratic complexity. When $n$ reaches millions, $n^2$ becomes an astronomical figure that no single server can handle.

The authors recognize that to handle big data, we don't just need "faster" algorithms; we need algorithms that are linearly scalable and native to parallel architectures like MapReduce.

Methodology: The "Democratic" Voting System

MR-DIS transforms the sequential DIS algorithm into a distributed workflow. The core "Insight" is that instance selection doesn't have to happen all at once; it can be a "democratic" process.

1. The Map Phase (Voting)

The dataset is partitioned into smaller, disjoint "bins." Each executor (Mapper) runs a standard instance selection algorithm (like Condensed Nearest Neighbor) on its subset. If an instance is marked for removal, it gets a "vote." This process is repeated across multiple rounds with different random partitions to ensure every instance is evaluated in multiple contexts.

2. The Reduce Phase (Consensus)

The Reducers aggregate the votes for each instance. To decide which instances are truly redundant, the algorithm calculates a Fitness Function: $f(v)=\alpha {ϵ}_t(v)+(1-\alpha )m(v)$ Where:

• ${ϵ}_t$ is the training error.
• $m$ is the percentage of instances kept.
• $\alpha$ is a user-defined trade-off between accuracy and size reduction.

Figure 1: The MapReduce design of MR-DIS, showing the transition from distributed voting to threshold calculation.

Experimental Validation: Near-Perfect Scalability

The authors tested MR-DIS on a Google DataProc cluster. The results confirm the primary hypothesis: increasing hardware leads to a proportional decrease in processing time.

Key Performance Insights:

• Linear Speedup: On the Susy dataset, the speedup remained almost linear up to 128 executors. The slight drop-off at 256 executors suggests a "saturation point" where the overhead of data distribution begins to outweigh the processing gains—a classic example of Amdahl's Law.
• Consistency: Unlike many distributed algorithms that trade accuracy for speed, MR-DIS maintains stable accuracy and compression rates regardless of the number of executors used.

Table 1: Filtering and Classification times show a clear halving of execution time whenever the number of executors is doubled.

Critical Analysis & Conclusion

MR-DIS is a significant contribution to the Big Data preprocessing toolbox. Its strength lies in its simplicity and its linear complexity. By moving the bottleneck from a single CPU to a distributed cluster, it makes 1-NN classification viable for datasets with millions of records.

Limitations:

1. Random Partitioning: The current version uses random partitioning, which might break local neighborhood structures.
2. Internal Algorithm: Currently supports CNN; more advanced pruning algorithms (like DROP series) have yet to be fully integrated.

Future Outlook: The authors suggest moving toward more "intelligent" partitioning methods, such as those inspired by Grand Tour theory, to better preserve the data's topological structure during the Map phase.

For practitioners working with Spark, MR-DIS offers a robust way to shrink data "fat" without losing the "muscle" of predictive performance.