Approximate Scalable Bounded Space Sketch for Large Data NLP

Amit Goyal, Hal Daumé IiiEMNLP 2011 · OpenReview

Abstract

We exploit sketch techniques, especially the Count-Min sketch, a memory, and time efficient framework which approximates the frequency of a word pair in the corpus without explicitly storing the word pair itself. These methods use hashing to deal with massive amounts of streaming text. We apply Count-Min sketch to approximate word pair counts and exhibit their effectiveness on three important NLP tasks. Our experiments demonstrate that on all of the three tasks, we get performance comparable to Exact word pair counts setting and state-of-the-art system. Our method scales to 49 GB of unzipped web data using bounded space of 2 billion counters (8 GB memory).

Introduction

In modern Natural Language Processing (NLP), the adage "more data is better data" holds true, yet processing massive corpora presents a significant memory bottleneck. Calculating relationships between words, such as Pointwise Mutual Information (PMI), requires counting word pair frequencies. However, the number of unique word pairs grows quadratically with vocabulary size, often reaching billions of entries. Storing these exactly requires either massive amounts of RAM or complex distributed clusters.

This paper addresses the challenge of scaling these computations to terabyte-sized datasets while keeping memory usage bounded. By utilizing "sketches"—probabilistic data structures—the authors demonstrate that large-scale NLP can be performed on a single machine with a tiny, fixed memory footprint.

Methodology: Count-Min Sketch and Conservative Updates

The core of this approach is the Count-Min (CM) Sketch, a sub-linear space data structure. A CM sketch consists of a 2D array of counters. When a word pair is processed, it is passed through multiple hash functions, each pointing to a specific cell in a different row of the array to be incremented. To estimate a count, one queries all hashed cells and takes the minimum value to minimize overestimation caused by hash collisions.

Average Relative Error for CM and CU sketches across different counter sizes and model depths.

A key contribution of this work is the Conservative Update (CU) heuristic. During an update, only the counters in rows currently holding the minimum value are incremented. As shown in Figure 3, this significantly reduces the average relative error compared to the standard CM sketch, particularly for lower-frequency items. To maintain high accuracy, the system uses a hybrid approach: exact counts for single words (which are relatively few) and the sketch for the massive volume of word pairs.

Experimental Evaluation

The authors evaluated the system on datasets ranging from the 9.8 GB Gigaword corpus to a 49 GB web-crawled dataset containing over 13 billion word pair tokens. Evaluation spanned three tasks: Semantic Orientation (SO), word similarity, and unsupervised dependency parsing.

Key Results

  • Semantic Orientation: Using sketch-based PMI, the system achieved ~82% accuracy in identifying word polarity, matching state-of-the-art systems. Figure 6 illustrates how accuracy improves with model size, rapidly approaching the performance of exact counting methods.
  • Word Similarity: Sketch-based distributional similarity scores achieved nearly identical correlation with human judgments (on WS-353 and RG-65) as exact counts.
  • Unsupervised Parsing: A "Large Data + Simple Rules" approach using the sketch achieved 39.9% accuracy on the Penn Treebank, outperforming complex baselines restricted to smaller datasets.
Accuracy of Semantic Orientation (SO) tasks using PMI and LLR as a function of model size, compared to exact counts.

Discussion and Conclusion

The experiments confirm that for many NLP tasks, exact counts are not strictly necessary; preserving the relative ranking of association scores is sufficient. The bounded space approach allows a standard desktop with 8GB of RAM to process 49GB of data with performance comparable to "infinite" memory systems.

While the Conservative Update improves accuracy, it introduces a trade-off by breaking the simple additivity (mergeability) of sketches, requiring specific protocols for distributed environments. Future work may extend these techniques to more complex structures like n-grams for machine translation and paraphrasing.

Summary updated

Abstract

We exploit sketch techniques, especially the Count-Min sketch, a memory, and time efficient framework which approximates the frequency of a word pair in the corpus without explicitly storing the word pair itself. These methods use hashing to deal with massive amounts of streaming text. We apply Count-Min sketch to approximate word pair counts and exhibit their effectiveness on three important NLP tasks. Our experiments demonstrate that on all of the three tasks, we get performance comparable to Exact word pair counts setting and state-of-the-art system. Our method scales to 49 GB of unzipped web data using bounded space of 2 billion counters (8 GB memory).
BibTeX
@inproceedings{goyal2011approximate,
  author = {Amit Goyal and Hal Daumé III},
  title = {{Approximate Scalable Bounded Space Sketch for Large Data NLP}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2011},
  url = {https://openreview.net/forum?id=r1WBefM_bS},
}
Figure