A Linguistic Knowledge Discovery Tool: Very Large Ngram Database Search with Arbitrary Wildcards

Satoshi SekineCOLING 2008

TL;DR

This paper introduces a novel ngram search tool designed for linguistic knowledge discovery. It enables rapid searching of massive ngram databases with arbitrary wildcard patterns, overcoming the limitations of existing search engines and custom-built systems, and making large-scale linguistic analysis accessible on a single PC.

What Problem Does This Paper Address?

Modern Natural Language Processing (NLP) increasingly relies on semantic analysis, which in turn requires extensive background knowledge. Gathering this knowledge, often referred to as the "knowledge bottleneck," has historically been a significant challenge. While the availability of vast text corpora and computational power has fueled research in knowledge discovery, existing methods often rely on local context and can be slow or limited when dealing with large datasets. Commercial search engines offer speed but suffer from restricted access, mysterious ranking, and unstable results. Building custom search engines is expensive and resource-intensive. This paper addresses the need for an efficient, accessible, and powerful tool that allows researchers with modest resources to explore massive ngram databases for linguistic knowledge discovery.

Methods

The core of the proposed tool is a trie-based search system. Unlike inverted indexing, which prioritizes indexing speed over search speed, the trie structure allows for faster searching, crucial for interactive exploration. The authors acknowledge that standard tries struggle with wildcard queries. To overcome this, they employ a clever strategy: instead of creating a separate trie for every possible wildcard combination, they construct a minimal set of "trie patterns" that can cover a wide range of wildcard search patterns. For instance, a single trie pattern can efficiently handle multiple ngram patterns with wildcards at different positions.

To manage the immense size of the ngram data, two key implementation techniques are used:

  1. Index Compression: They reduce the size of trie nodes by deleting redundant suffix information and storing only ngram IDs. This compressed data is then stored in a master database, saving significant space.
  2. Pointer Elimination: By recognizing that ngram data is static (no insertions or replacements), they eliminate parent and sibling pointers within the trie nodes, further reducing index size.

The large tries are further divided into manageable segments that can fit into modest memory. They also utilize memory mapping (mmap) to load only the necessary portions of the trie segments into memory from disk.

Datasets

The system was implemented and evaluated using two large ngram datasets:

  • Google 1T Web 5gram: A portion of the 5-gram data derived from approximately 1 trillion word tokens of publicly accessible web pages.
  • 9-grams from 82 years of newspaper: This dataset was compiled from various newspaper corpora (including NANTC, LATWP, NYT, REUFF, REUTE, WSJ, BBN GigaWord, People Daily, Taipei Times, The Hindu, Arab News, Gulf News, India Times, AQUAINT, and CSR) and cleaned to reduce noise.

Key Insights and Ideas

  • The "Knowledge Bottleneck" is Real: The paper highlights the ongoing challenge of acquiring the vast background knowledge needed for advanced NLP tasks.
  • Tries for Speed, but Wildcards are Tricky: While tries are excellent for fast exact matching, their structure makes wildcard queries inefficient without specialized handling.
  • Minimal Trie Patterns for Maximum Coverage: The core innovation is the idea of creating a reduced set of "trie patterns" that can efficiently cover a broad spectrum of wildcard search queries, significantly reducing the complexity and number of required search structures.
  • Compression is Key for Scale: Aggressive index compression techniques are essential for fitting massive ngram datasets into practical hardware constraints.
  • Accessibility Matters: The goal is to democratize large-scale linguistic analysis, making it feasible for researchers without access to supercomputing clusters.

Key Results

  • Speed: The tool can perform searches in a fraction of a second for most reasonable queries. For example, the speed evaluation on 9-grams showed search times of 19ms for original queries and 29ms for queries with wildcards, with an average of only 1.26 returned ngrams.
  • Resource Efficiency: The system runs on a single Linux PC with reasonable memory (4GB) and disk space (less than 400GB).
  • Wildcard Support: The tool successfully supports queries with an arbitrary number of wildcards, returning both the fillers of the wildcards and ngram frequencies.
  • Index Size Reduction: The implementation techniques achieved significant index size reductions (e.g., >50% for 9-grams).

Limitations and Future Work

  • Index Creation Time: While search is fast, the initial creation of the index is a substantial undertaking, taking months on multiple machines or about a week on a single 64GB machine.
  • Contextual Depth: The authors acknowledge that while 9-grams offer more context than 5-grams, longer contexts might be necessary for certain knowledge discovery tasks.
  • Future Work: The authors plan to improve the tool by displaying original sentences from which ngrams are extracted, providing richer context. They also aim to apply this tool to find linguistic knowledge for specific NLP applications.

Summary updated

BibTeX
@inproceedings{sekine2008linguistic,
  author = {Satoshi Sekine},
  title = {{A Linguistic Knowledge Discovery Tool: Very Large Ngram Database Search with Arbitrary Wildcards}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2008},
}
Figure