Using sketches to estimate associations

Ping Li; Kenneth W. Church

doi:10.3115/1220575.1220664

Using sketches to estimate associations

Ping Li, Kenneth W. Church

Research output: Contribution to conference › Paper › peer-review

25 Scopus citations

Abstract

We should not have to look at the entire corpus (e.g., the Web) to know if two words are associated or not.¹ A powerful sampling technique called Sketches was originally introduced to remove duplicate Web pages. We generalize sketches to estimate contingency tables and associations, using a maximum likelihood estimator to find the most likely contingency table given the sample, the margins (document frequencies) and the size of the collection. Not unsurprisingly, computational work and statistical accuracy (variance or errors) depend on sampling rate, as will be shown both theoretically and empirically. Sampling methods become more and more important with larger and larger collections. AtWeb scale, sampling rates as low as 10^-4 may suffice.

Original language	English (US)
Pages	708-715
Number of pages	8
DOIs	https://doi.org/10.3115/1220575.1220664
State	Published - 2005
Externally published	Yes
Event	Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, HLT/EMNLP 2005, Co-located with the 2005 Document Understanding Conference, DUC and the 9th International Workshop on Parsing Technologies, IWPT - Vancouver, BC, Canada Duration: Oct 6 2005 → Oct 8 2005

Other

Other	Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, HLT/EMNLP 2005, Co-located with the 2005 Document Understanding Conference, DUC and the 9th International Workshop on Parsing Technologies, IWPT
Country/Territory	Canada
City	Vancouver, BC
Period	10/6/05 → 10/8/05

All Science Journal Classification (ASJC) codes

Computational Theory and Mathematics
Computer Science Applications
Information Systems

Access to Document

10.3115/1220575.1220664

Cite this

Li, P., & Church, K. W. (2005). Using sketches to estimate associations. 708-715. Paper presented at Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, HLT/EMNLP 2005, Co-located with the 2005 Document Understanding Conference, DUC and the 9th International Workshop on Parsing Technologies, IWPT, Vancouver, BC, Canada. https://doi.org/10.3115/1220575.1220664

@conference{9dacf3b52d624e5495d8429830c793f9,

title = "Using sketches to estimate associations",

abstract = "We should not have to look at the entire corpus (e.g., the Web) to know if two words are associated or not.1 A powerful sampling technique called Sketches was originally introduced to remove duplicate Web pages. We generalize sketches to estimate contingency tables and associations, using a maximum likelihood estimator to find the most likely contingency table given the sample, the margins (document frequencies) and the size of the collection. Not unsurprisingly, computational work and statistical accuracy (variance or errors) depend on sampling rate, as will be shown both theoretically and empirically. Sampling methods become more and more important with larger and larger collections. AtWeb scale, sampling rates as low as 10-4 may suffice.",

author = "Ping Li and Church, {Kenneth W.}",

year = "2005",

doi = "10.3115/1220575.1220664",

language = "English (US)",

pages = "708--715",

note = "Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, HLT/EMNLP 2005, Co-located with the 2005 Document Understanding Conference, DUC and the 9th International Workshop on Parsing Technologies, IWPT ; Conference date: 06-10-2005 Through 08-10-2005",

}

Li, P & Church, KW 2005, 'Using sketches to estimate associations', Paper presented at Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, HLT/EMNLP 2005, Co-located with the 2005 Document Understanding Conference, DUC and the 9th International Workshop on Parsing Technologies, IWPT, Vancouver, BC, Canada, 10/6/05 - 10/8/05 pp. 708-715. https://doi.org/10.3115/1220575.1220664

Using sketches to estimate associations. / Li, Ping; Church, Kenneth W.

2005. 708-715 Paper presented at Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, HLT/EMNLP 2005, Co-located with the 2005 Document Understanding Conference, DUC and the 9th International Workshop on Parsing Technologies, IWPT, Vancouver, BC, Canada.

Research output: Contribution to conference › Paper › peer-review

TY - CONF

T1 - Using sketches to estimate associations

AU - Li, Ping

AU - Church, Kenneth W.

PY - 2005

Y1 - 2005

N2 - We should not have to look at the entire corpus (e.g., the Web) to know if two words are associated or not.1 A powerful sampling technique called Sketches was originally introduced to remove duplicate Web pages. We generalize sketches to estimate contingency tables and associations, using a maximum likelihood estimator to find the most likely contingency table given the sample, the margins (document frequencies) and the size of the collection. Not unsurprisingly, computational work and statistical accuracy (variance or errors) depend on sampling rate, as will be shown both theoretically and empirically. Sampling methods become more and more important with larger and larger collections. AtWeb scale, sampling rates as low as 10-4 may suffice.

AB - We should not have to look at the entire corpus (e.g., the Web) to know if two words are associated or not.1 A powerful sampling technique called Sketches was originally introduced to remove duplicate Web pages. We generalize sketches to estimate contingency tables and associations, using a maximum likelihood estimator to find the most likely contingency table given the sample, the margins (document frequencies) and the size of the collection. Not unsurprisingly, computational work and statistical accuracy (variance or errors) depend on sampling rate, as will be shown both theoretically and empirically. Sampling methods become more and more important with larger and larger collections. AtWeb scale, sampling rates as low as 10-4 may suffice.

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

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

U2 - 10.3115/1220575.1220664

DO - 10.3115/1220575.1220664

M3 - Paper

AN - SCOPUS:35748938363

SP - 708

EP - 715

T2 - Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, HLT/EMNLP 2005, Co-located with the 2005 Document Understanding Conference, DUC and the 9th International Workshop on Parsing Technologies, IWPT

Y2 - 6 October 2005 through 8 October 2005

ER -

Li P, Church KW. Using sketches to estimate associations. 2005. Paper presented at Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, HLT/EMNLP 2005, Co-located with the 2005 Document Understanding Conference, DUC and the 9th International Workshop on Parsing Technologies, IWPT, Vancouver, BC, Canada. doi: 10.3115/1220575.1220664

Using sketches to estimate associations

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this