Abstract
This paper explores the challenge of scaling up language processing algorithms to increasingly large datasets. While cluster computing has been available in commercial environments for several years, academic researchers have fallen behind in their ability to work on large datasets. I discuss two barriers contributing to this problem: lack of a suitable programming model for managing concurrency and difficulty in obtaining access to hardware. Hadoop, an open-source implementation of Google's MapReduce framework, provides a compelling solution to both issues. Its simple programming model hides system-level details from the developer, and its ability to run on commodity hardware puts cluster computing within the reach of many academic research groups. This paper illustrates these points with a case study in building word co-occurrence matrices from large corpora. I conclude with an analysis of an alternative computing model based on renting instead of buying computer clusters.
Introduction
In the mid-2000s, Natural Language Processing (NLP) transitioned heavily toward empirical, data-driven methods. It became evident that for many tasks, the volume of training data was more critical than the complexity of the machine learning algorithm. However, this shift created a significant divide. Large technology companies possessed the massive computing clusters required to process "Web-scale" data, while academic researchers remained constrained by individual workstations. This "data gap" was driven by two primary barriers: the complexity of parallel programming and the prohibitive cost of hardware.
Methods: MapReduce and Algorithmic Design
To address the programming hurdle, this study utilizes MapReduce, specifically the open-source Hadoop implementation. MapReduce simplifies distributed computing by abstracting away low-level details like concurrency, synchronization, and hardware failure.
The core of this case study involves building a word co-occurrence matrix, a fundamental NLP task that counts the frequency of word pairs appearing within a specific window. Two distinct strategies are compared:
- The "Pairs" Approach: The mapper emits a key-value pair for every co-occurring word pair (e.g.,
((word1, word2), 1)). The reducer then aggregates these counts. While conceptually simple, this approach generates a massive volume of intermediate keys, leading to significant network congestion during the "shuffle" phase. - The "Stripes" Approach: The mapper aggregates counts locally into an associative array (a "stripe") for each word (e.g.,
(word1, {word2: 5, word3: 2, ...})). The reducer performs an element-wise sum of these arrays. This method trades local memory for a drastic reduction in network traffic.
Experimental Setup
Experiments were conducted using the English Gigaword corpus (version 3), containing approximately 3 billion words (19.4 GB uncompressed). A subset, the APW sub-corpus (2.27 million documents), was also used for comparative analysis. To address the hardware barrier, the study explored "Utility Computing" via Amazon EC2, testing the viability of renting virtualized clusters.
Results and Discussion
The "stripes" approach demonstrated superior efficiency, running 5.7 times faster than the "pairs" approach on the APW sub-corpus (11 minutes versus 62 minutes). Crucially, both algorithms exhibited near-perfect linear scalability, indicating that processing time scales predictably with data size.
The investigation into utility computing revealed that "renting" cycles is a paradigm shift for academic research. By scaling from 20 to 80 machines on Amazon EC2, the author was able to build a full co-occurrence matrix for the entire 3-billion-word corpus for less than $3.00.
Conclusion
The combination of MapReduce and cloud computing effectively democratizes "big data" processing. The "stripes" method illustrates that scalability requires rethinking data structures to prioritize local aggregation and minimize network bottlenecks. By leveraging platforms like Amazon EC2, small research groups can perform web-scale NLP experiments at a fraction of the cost of maintaining dedicated hardware, bridging the gap between academia and industry.
Summary updated