Intermediate N-Gramming: Deterministic and Fast N-Grams For Large N and Large Datasets
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917090395422720 |
|---|---|
| author | Curtin, Ryan R. Lu, Fred Raff, Edward Ranade, Priyanka |
| author_facet | Curtin, Ryan R. Lu, Fred Raff, Edward Ranade, Priyanka |
| contents | The number of n-gram features grows exponentially in n, making it computationally demanding to compute the most frequent n-grams even for n as small as 3. Motivated by our production machine learning system built on n-gram features, we ask: is it possible to accurately, deterministically, and quickly recover the top-k most frequent n-grams? We devise a multi-pass algorithm called Intergrams that constructs candidate n-grams from the preceding (n - 1)-grams. By designing this algorithm with hardware in mind, our approach yields more than an order of magnitude speedup (up to 33x!) over the next known fastest algorithm, even when similar optimizations are applied to the other algorithm. Using the empirical power-law distribution over n-grams, we also provide theory to inform the efficacy of our multi-pass approach. Our code is available at https://github.com/rcurtin/Intergrams. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_14955 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Intermediate N-Gramming: Deterministic and Fast N-Grams For Large N and Large Datasets Curtin, Ryan R. Lu, Fred Raff, Edward Ranade, Priyanka Data Structures and Algorithms The number of n-gram features grows exponentially in n, making it computationally demanding to compute the most frequent n-grams even for n as small as 3. Motivated by our production machine learning system built on n-gram features, we ask: is it possible to accurately, deterministically, and quickly recover the top-k most frequent n-grams? We devise a multi-pass algorithm called Intergrams that constructs candidate n-grams from the preceding (n - 1)-grams. By designing this algorithm with hardware in mind, our approach yields more than an order of magnitude speedup (up to 33x!) over the next known fastest algorithm, even when similar optimizations are applied to the other algorithm. Using the empirical power-law distribution over n-grams, we also provide theory to inform the efficacy of our multi-pass approach. Our code is available at https://github.com/rcurtin/Intergrams. |
| title | Intermediate N-Gramming: Deterministic and Fast N-Grams For Large N and Large Datasets |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.14955 |