Fast Algorithms for Learning with Long $N$-grams via Suffix Tree Based Matrix Multiplication

Hristo Paskov, Trevor Hastie, John Mitchell
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:840-849, 2015.

Abstract

This paper addresses the computational and statistical issues of learning with long – and possibly all – $N$-grams in a document corpus. We leverage the rich algebraic structure of $N$-gram matrices to provide a data structure which can store and multiply any $N$-gram matrix in memory and time that is, at worst, linear in the length of the corpus from which it is derived. As matrix-vector multiplication lies at the heart of most machine learning algorithms, our algorithm can speed up any learning procedure that uses $N$-gram features and has such structure. We also provide an efficient, linear running time and memory, framework that produces our data structure and screens $N$-gram features according to a multitude of statistical criteria. We demonstrate the performance of our algorithm on natural language and DNA sequence datasets; the computational and memory savings are substantial. Finally, we apply our framework to several large-scale sentiment analysis problems involving millions of reviews over gigabytes of text and show that higher-order $N$-grams can substantially improve performance.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-paskov15a, title = {Fast Algorithms for Learning with Long $N$-grams via Suffix Tree Based Matrix Multiplication}, author = {Paskov, Hristo and Hastie, Trevor and Mitchell, John}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {840--849}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/paskov15a/paskov15a.pdf}, url = {https://proceedings.mlr.press/r13/paskov15a.html}, abstract = {This paper addresses the computational and statistical issues of learning with long – and possibly all – $N$-grams in a document corpus. We leverage the rich algebraic structure of $N$-gram matrices to provide a data structure which can store and multiply any $N$-gram matrix in memory and time that is, at worst, linear in the length of the corpus from which it is derived. As matrix-vector multiplication lies at the heart of most machine learning algorithms, our algorithm can speed up any learning procedure that uses $N$-gram features and has such structure. We also provide an efficient, linear running time and memory, framework that produces our data structure and screens $N$-gram features according to a multitude of statistical criteria. We demonstrate the performance of our algorithm on natural language and DNA sequence datasets; the computational and memory savings are substantial. Finally, we apply our framework to several large-scale sentiment analysis problems involving millions of reviews over gigabytes of text and show that higher-order $N$-grams can substantially improve performance.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Fast Algorithms for Learning with Long $N$-grams via Suffix Tree Based Matrix Multiplication %A Hristo Paskov %A Trevor Hastie %A John Mitchell %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-paskov15a %I PMLR %P 840--849 %U https://proceedings.mlr.press/r13/paskov15a.html %V R13 %X This paper addresses the computational and statistical issues of learning with long – and possibly all – $N$-grams in a document corpus. We leverage the rich algebraic structure of $N$-gram matrices to provide a data structure which can store and multiply any $N$-gram matrix in memory and time that is, at worst, linear in the length of the corpus from which it is derived. As matrix-vector multiplication lies at the heart of most machine learning algorithms, our algorithm can speed up any learning procedure that uses $N$-gram features and has such structure. We also provide an efficient, linear running time and memory, framework that produces our data structure and screens $N$-gram features according to a multitude of statistical criteria. We demonstrate the performance of our algorithm on natural language and DNA sequence datasets; the computational and memory savings are substantial. Finally, we apply our framework to several large-scale sentiment analysis problems involving millions of reviews over gigabytes of text and show that higher-order $N$-grams can substantially improve performance. %Z Reissued by PMLR on 04 October 2026.
APA
Paskov, H., Hastie, T. & Mitchell, J.. (2015). Fast Algorithms for Learning with Long $N$-grams via Suffix Tree Based Matrix Multiplication. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:840-849 Available from https://proceedings.mlr.press/r13/paskov15a.html. Reissued by PMLR on 04 October 2026.

Related Material