# Heaps’ law

Heaps’ law describes the portion of a vocabulary which is represented by an instance document (or set of instance documents) consisting of words chosen from the vocabulary. This can be formulated as

 $V_{R}(n)=Kn^{\beta}$

Where $V_{R}$ is the portion of the vocabulary $V$ ($V_{R}\subseteq V$) represented by the instance text of size $n$. $K$ and $\beta$ are free parameters determined empirically.

With English text corpuses, typically $K$ is between 10 and 100, and $.4\leq\beta\leq.6$.

Heaps’ law means that as more instance text is gathered, there will be diminishing returns in terms of discovery of the full vocabulary from which the distinct terms are drawn.

It is interesting to note that Heaps’ law applies in the general case where the “vocabulary” is just some set of distinct types which are attributes of some collection of objects. For example, the objects could be people, and the types could be country of origin of the person. If persons are selected randomly (that is, we are not selecting based on country of origin), then Heaps’ law says we will quickly have representatives from most countries (in proportion to their population) but it will become increasingly difficult to cover the entire set of countries by continuing this method of sampling.

## 1 References

• Baeza-Yates and Ribeiro-Neto, Modern Information Retrieval, ACM Press, 1999.

Title Heaps’ law HeapsLaw 2013-03-22 13:01:56 2013-03-22 13:01:56 akrowne (2) akrowne (2) 6 akrowne (2) Definition msc 94A99 msc 68P20 msc 60E05