Sampling from a long tailed distribution I have about 500K records from a dataset that consists of counts (so every record is a count of something, like the number of attempts by an IP address to connect to a website).
I know, a priori, that each record belongs to one of two groups (for example malicious IPs and legitimate IPs), but I don't know which one without manually inspecting the record and determining the grouping. 
I also know that the distribution of counts is very long tailed (both looking at my 500K sample and a priori knowledge.)  
In order to get a better idea of how the grouping changes as the counts value increases, I'd like to take a reasonably small sample of records (say, no more than 1000) to examine manually. What is the right way to sample this data, considering that a simple random sample would miss the tail? 
 A: I suggest a stratified sample, where you divide the IPs into groups that cover the entire range of counts, including the long tail. There are two choices:
1) divide the range of counts into H strata with equal numbers of IPs in each
2) divide into H strata with equal  count totals in each.
In either case, draw a simple random sample of the same size from each stratum. So if the overall sample size is $n$ and the number of strata is $H$, take $n_* = n/H$ observations per stratum.
If the distribution of counts is roughly of the form of a triangle with mode on the left and a long tail on  the right, the first solution will have most observations devoted to lower count IPs. This is probably not optimum if the malicious IPs are likely to have  higher counts.  The second approach is best for this situation, as it puts more observations among the higher count IPs.
The first solution has the advantage of a simpler descriptive analysis, as all observations will be equally weighted. Thus the  sample proportion of IPs that are malicious will estimate the population the proportion.
The second approach will require specification of sampling weights. But you would need a survey sampling program in any case  to get the best standard error. The stratum boundaries in the second approach will be irregular, so I suggest that you re-categorize counts before presenting the results. 
How many strata? How many observations? Perhaps H = 10 to 20 strata should be okay.  But n = 1,000 seems like too many to me. You might draw that many, but evaluate only a random half-sample in each stratum, doing more if standard errors are too big. To guide your choices, just notice that the maximum standard error for the. proportion malicious in any stratum will be at most $0.5/\sqrt{n_*}$.
