A theoretical model for n-gram distribution in big data corpora

Joaquim F. Silva; Carlos Gonçalves; José C. Cunha

doi:10.1109/BigData.2016.7840598

A theoretical model for n-gram distribution in big data corpora

Joaquim F. Silva, Carlos Gonçalves, José C. Cunha

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

Abstract

There is a wide diversity of applications relying on the identification of the sequences of n consecutive words (n-grams) occurring in corpora. Many studies follow an empirical approach for determining the statistical distribution of the n-grams but are usually constrained by the corpora sizes, which for practical reasons stay far away from Big Data. However, Big Data sizes imply hidden behaviors to the applications, such as extraction of relevant information from Web scale sources. In this paper we propose a theoretical approach for estimating the number of distinct n-grams in each corpus. It is based on the Zipf-Mandelbrot Law and the Poisson distribution, and it allows an efficient estimation of the number of distinct 1-grams, 2-grams,..., 6-grams, for any corpus size. The proposed model was validated for English and French corpora. We illustrate a practical application of this approach to the extraction of relevant expressions from natural language corpora, and predict its asymptotic behaviour for increasingly large sizes.

Original language	English
Title of host publication	Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016
Editors	Ronay Ak, George Karypis, Yinglong Xia, Xiaohua Tony Hu, Philip S. Yu, James Joshi, Lyle Ungar, Ling Liu, Aki-Hiro Sato, Toyotaro Suzumura, Sudarsan Rachuri, Rama Govindaraju, Weijia Xu
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	134-141
Number of pages	8
ISBN (Electronic)	9781467390040
DOIs	https://doi.org/10.1109/BigData.2016.7840598
Publication status	Published - 1 Jan 2016
Event	4th IEEE International Conference on Big Data, Big Data 2016 - Washington, United States Duration: 5 Dec 2016 → 8 Dec 2016

Conference

Conference	4th IEEE International Conference on Big Data, Big Data 2016
Country	United States
City	Washington
Period	5/12/16 → 8/12/16

Keywords

Big Data
Extraction of Relevant Expressions
n-gram Models
Poisson Distribution
Zipf-Mandelbrot Law

Access to Document

10.1109/BigData.2016.7840598

Link to publication in Scopus

Fingerprint Dive into the research topics of 'A theoretical model for n-gram distribution in big data corpora'. Together they form a unique fingerprint.

Cite this

Silva, J. F., Gonçalves, C., & Cunha, J. C. (2016). A theoretical model for n-gram distribution in big data corpora. In R. Ak, G. Karypis, Y. Xia, X. T. Hu, P. S. Yu, J. Joshi, L. Ungar, L. Liu, A-H. Sato, T. Suzumura, S. Rachuri, R. Govindaraju, ... W. Xu (Eds.), Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016 (pp. 134-141). [7840598] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BigData.2016.7840598

Silva, Joaquim F. ; Gonçalves, Carlos ; Cunha, José C. / A theoretical model for n-gram distribution in big data corpora. Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016. editor / Ronay Ak ; George Karypis ; Yinglong Xia ; Xiaohua Tony Hu ; Philip S. Yu ; James Joshi ; Lyle Ungar ; Ling Liu ; Aki-Hiro Sato ; Toyotaro Suzumura ; Sudarsan Rachuri ; Rama Govindaraju ; Weijia Xu. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 134-141

@inproceedings{042e3fb1749a4f909867d6b22582154e,

title = "A theoretical model for n-gram distribution in big data corpora",

abstract = "There is a wide diversity of applications relying on the identification of the sequences of n consecutive words (n-grams) occurring in corpora. Many studies follow an empirical approach for determining the statistical distribution of the n-grams but are usually constrained by the corpora sizes, which for practical reasons stay far away from Big Data. However, Big Data sizes imply hidden behaviors to the applications, such as extraction of relevant information from Web scale sources. In this paper we propose a theoretical approach for estimating the number of distinct n-grams in each corpus. It is based on the Zipf-Mandelbrot Law and the Poisson distribution, and it allows an efficient estimation of the number of distinct 1-grams, 2-grams,..., 6-grams, for any corpus size. The proposed model was validated for English and French corpora. We illustrate a practical application of this approach to the extraction of relevant expressions from natural language corpora, and predict its asymptotic behaviour for increasingly large sizes.",

keywords = "Big Data, Extraction of Relevant Expressions, n-gram Models, Poisson Distribution, Zipf-Mandelbrot Law",

author = "Silva, {Joaquim F.} and Carlos Gon{\cc}alves and Cunha, {Jos{\'e} C.}",

year = "2016",

month = "1",

day = "1",

doi = "10.1109/BigData.2016.7840598",

language = "English",

pages = "134--141",

editor = "Ronay Ak and George Karypis and Yinglong Xia and Hu, {Xiaohua Tony} and Yu, {Philip S.} and James Joshi and Lyle Ungar and Ling Liu and Aki-Hiro Sato and Toyotaro Suzumura and Sudarsan Rachuri and Rama Govindaraju and Weijia Xu",

booktitle = "Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

}

Silva, JF, Gonçalves, C & Cunha, JC 2016, A theoretical model for n-gram distribution in big data corpora. in R Ak, G Karypis, Y Xia, XT Hu, PS Yu, J Joshi, L Ungar, L Liu, A-H Sato, T Suzumura, S Rachuri, R Govindaraju & W Xu (eds), Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016., 7840598, Institute of Electrical and Electronics Engineers Inc., pp. 134-141, 4th IEEE International Conference on Big Data, Big Data 2016, Washington, United States, 5/12/16. https://doi.org/10.1109/BigData.2016.7840598

A theoretical model for n-gram distribution in big data corpora. / Silva, Joaquim F.; Gonçalves, Carlos; Cunha, José C.

Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016. ed. / Ronay Ak; George Karypis; Yinglong Xia; Xiaohua Tony Hu; Philip S. Yu; James Joshi; Lyle Ungar; Ling Liu; Aki-Hiro Sato; Toyotaro Suzumura; Sudarsan Rachuri; Rama Govindaraju; Weijia Xu. Institute of Electrical and Electronics Engineers Inc., 2016. p. 134-141 7840598.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A theoretical model for n-gram distribution in big data corpora

AU - Silva, Joaquim F.

AU - Gonçalves, Carlos

AU - Cunha, José C.

PY - 2016/1/1

Y1 - 2016/1/1

N2 - There is a wide diversity of applications relying on the identification of the sequences of n consecutive words (n-grams) occurring in corpora. Many studies follow an empirical approach for determining the statistical distribution of the n-grams but are usually constrained by the corpora sizes, which for practical reasons stay far away from Big Data. However, Big Data sizes imply hidden behaviors to the applications, such as extraction of relevant information from Web scale sources. In this paper we propose a theoretical approach for estimating the number of distinct n-grams in each corpus. It is based on the Zipf-Mandelbrot Law and the Poisson distribution, and it allows an efficient estimation of the number of distinct 1-grams, 2-grams,..., 6-grams, for any corpus size. The proposed model was validated for English and French corpora. We illustrate a practical application of this approach to the extraction of relevant expressions from natural language corpora, and predict its asymptotic behaviour for increasingly large sizes.

AB - There is a wide diversity of applications relying on the identification of the sequences of n consecutive words (n-grams) occurring in corpora. Many studies follow an empirical approach for determining the statistical distribution of the n-grams but are usually constrained by the corpora sizes, which for practical reasons stay far away from Big Data. However, Big Data sizes imply hidden behaviors to the applications, such as extraction of relevant information from Web scale sources. In this paper we propose a theoretical approach for estimating the number of distinct n-grams in each corpus. It is based on the Zipf-Mandelbrot Law and the Poisson distribution, and it allows an efficient estimation of the number of distinct 1-grams, 2-grams,..., 6-grams, for any corpus size. The proposed model was validated for English and French corpora. We illustrate a practical application of this approach to the extraction of relevant expressions from natural language corpora, and predict its asymptotic behaviour for increasingly large sizes.

KW - Big Data

KW - Extraction of Relevant Expressions

KW - n-gram Models

KW - Poisson Distribution

KW - Zipf-Mandelbrot Law

UR - http://www.scopus.com/inward/record.url?scp=85015200225&partnerID=8YFLogxK

U2 - 10.1109/BigData.2016.7840598

DO - 10.1109/BigData.2016.7840598

M3 - Conference contribution

AN - SCOPUS:85015200225

SP - 134

EP - 141

BT - Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016

A2 - Ak, Ronay

A2 - Karypis, George

A2 - Xia, Yinglong

A2 - Hu, Xiaohua Tony

A2 - Yu, Philip S.

A2 - Joshi, James

A2 - Ungar, Lyle

A2 - Liu, Ling

A2 - Sato, Aki-Hiro

A2 - Suzumura, Toyotaro

A2 - Rachuri, Sudarsan

A2 - Govindaraju, Rama

A2 - Xu, Weijia

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Silva JF, Gonçalves C, Cunha JC. A theoretical model for n-gram distribution in big data corpora. In Ak R, Karypis G, Xia Y, Hu XT, Yu PS, Joshi J, Ungar L, Liu L, Sato A-H, Suzumura T, Rachuri S, Govindaraju R, Xu W, editors, Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 134-141. 7840598 https://doi.org/10.1109/BigData.2016.7840598