Assume that we observe some objects (e.g. people, car models, etc.). Our task is to sort objects based on their frequency of observation. For example, Here is the top 5 best-selling cars in America:

  1. Toyota Camry, count = 26,848

  2. Honda Civic, count = 26,741

  3. Toyota Corolla, count = 22,362

  4. Nissan Altima, count = 22,156

  5. Honda Accord, count = 20,765

More formally, assume we have n items: $a_1,a_2,\ldots,a_n$, with their observed counts $c_1,c_2,\ldots,c_n$. All we want to do is to sort them by frequencies (counts).

Since counting might be expensive, we might want to sample the counts (e.g. use $1\%$ of sales) and sort our items (cars) by their frequency in the sample set.

Question: What is the minimum sample size, such that the sorting is not affected [too much]?

An error occurs when the position of an object in the list is changed, e.g. the count of Nissan Altima in the sample set is less Honda Accord's one. We want to minimize or bound such errors by proper sample size.

Are there any theories for this problem (sample size for ranking)? what are the keywords?


1 Answer 1


This is a difficult question to answer without having an idea of how large the differences are. For example, if $max(c_i - c_j) = 5$ $\forall i,j$ then good luck. On the other hand, if $min(c_i - c_j) = 10,000$ $\forall i,j$ then your sample size doesn't have to be very large. Check out "data sketches" and for an example the frequency section on the blog data sketches .

My suggestion would be to run multiple (say 10^3) smaller sample counters. If the results seem robust then you're good. If not, increase sample size.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.