1
$\begingroup$

One of the developers of lobste.rs recently posted some interesting data showing the distribution of votes and comments for stories on the site. In particular, the posted results give a histogram of the number of stories with a given number of comments/votes rounded to the nearest 10. For example, two stories with a vote count of 7 and 12 would both add to the count of the "10" bin.

This data should allow the creation of a workload generator, a program that produces a sequence of operations that mimic the requests that would be generated by the real site. Such a tool would be very useful for evaluating, e.g., different backend databases for the site. However, this requires some analysis of the data that I can't quite wrap my head around. For clarity, let's focus on the number of votes per story. Specifically, the problem is the following:

Given a count of story IDs with a each number of votes rounded to the nearest 10 (the posted data), produce a sequence of story IDs that approximates the vote proportions in the posted data.

To make it more concrete: if the data was {{0, 10}, {10, 3}, {20, 1}} (so there must be 10+3+1 story IDs), produce a sequence like [a, a, a, b, a, a, c, a, b, d, a, ...] such that the proportion of as is $25/(1\times25 + 3\times15 + 10\times5)$, the proportion of bs is $15/(1\times25 + 3\times*15 + 10\times5)$, and similarly for c and d. e through the last story ID should each appear with probability $5/(1\times25 + 3\times15 + 10\times5)$.

We can produce such a sequence naively if we store a list of (start, id) where start is the total count of votes for all preceeding story IDs. To sample, we pick a random number r in $[0, 1\times25 + 3\times*15 + 10\times5)$, and then choose the id from the item in the list with the smallest start > r. However, this is somewhat slow, as it requires either a binary search or a tree structure. Instead, I want to know if there's a way to do this more efficiently by estimating the distribution that produced the histogram, and then sampling from that distribution?

There are a number of threads on estimating a distribution from a histogram or using fitdistr. There's even one on sampling from a distribution given by a histogram. Along similar lines, this thread on assessing approximate distribution of data based on a histogram has a number of neat examples. But none of these seem (at least to my non-statistician eyes) as though they'd be able to satisfy this particular use-case. At least not in isolation?

I'd love to hear your take on how this problem might be tackled with a more sophisticated solution than my brute-force naive solution above!

$\endgroup$
1
$\begingroup$

Better than using the histogram, just sample with replacement from the data used to construct the histogram. That is called bootstrapping, search this site.

If you don't have the original data, but just a histogram, construct some quasi-data from the histogram and do as above. If you don't even have the original sample size, that might be difficult. Then sample one of the histogram bars with probability proportional to its area, then draw from a uniform distribution on the interval covered by that bar.

$\endgroup$
  • $\begingroup$ Yeah, unfortunately I do not have access to the underlying data. Otherwise this'd be a lot easier :) Your proposed method of sampling with probabilities proportional to the area of each bar is what I ended up using in my Rust implementation, though I was hoping we could do better by approximating the underlying distribution that generated the histogram. May be too tricky though. $\endgroup$ – Jon Gjengset Mar 19 '18 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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