RE: st: approximate quantiles in Stata

[Joe Canner <jcanner1@jhmi.edu>]

Laszlo,

My guess is that Stata has already optimized -sort- about as much as it can be optimized.  The algorithm you linked to earlier appeared to be more geared at calculating quantiles in real time (in a data stream) rather than in a static sample.  Given that a Stata data set is already in memory (and getting it into memory takes a significant amount of time in and of itself for a large data set), I doubt if that algorithm is going to buy you anything above and beyond using the standard Stata sort.

This is an intriguing problem, though, one which I would probably benefit from as well (we typically process datasets with millions of observations as well), so I will keep my eyes open for quantile algorithms.  Keep us posted if you find anything interesting that could easily be turned into a user-written algorithm,

Regards,
Joe Canner
Johns Hopkins University School of Medicine
________________________________________
From: owner-statalist@hsphsun2.harvard.edu [owner-statalist@hsphsun2.harvard.edu] on behalf of László Sándor [sandorl@gmail.com]
Sent: Saturday, August 24, 2013 12:03 PM
To: statalist@hsphsun2.harvard.edu
Subject: Re: st: approximate quantiles in Stata

Also, I received a quick comment from theoretical CS people that the
quantile thing could be faster than the quoted speed of sorting in
Stata (and xtile does sort): "It is possible to find the quantiles in
O(N) using a straightforward modification of the selection algorithm
based on quicksort (see
http://en.wikipedia.org/wiki/Selection_algorithm)."
http://cstheory.stackexchange.com/questions/18732/algorithms-to-split-data-into-roughly-equal-sized-quantiles/

Is there anything to know about QuickSort in Stata?

That said, I cannot write up a fancy algorithm to find the quantiles,
let alone a whole new -sort-, so probably the question is still about
sensible downsampling.

On Sat, Aug 24, 2013 at 7:42 AM, László Sándor <sandorl@gmail.com> wrote:
> Thanks, David,
>
> I think the typical use case is about tens of millions of
> observations. (And as I think it matters for precision, the typical
> case is about 20 bins, or vingtiles.)
>
> FWIW, I also tried to profile -xtile- with maximum number of
> observations possible. With Stata 13 running on 64 cores, it took 7
> hours to generate vingtiles.
>
> Laszlo
>
> On Fri, Aug 23, 2013 at 9:54 PM, David Hoaglin <dchoaglin@gmail.com> wrote:
>> Hi, Laszlo.
>>
>> How large are your samples, and which quantiles do you need?
>>
>> I think I saw some relevant work a number of years ago, and I will
>> have to look for it.
>>
>> David Hoaglin
>>
>> On Fri, Aug 23, 2013 at 9:01 PM, László Sándor <sandorl@gmail.com> wrote:
>>> Hi,
>>> My work is slowed down by the precise but computationally intensive
>>> quantile calculation of Stata. I am curious if there are any
>>> approximation algorithms implemented out there, something along these
>>> ideas: http://www.prelert.com/blog/q-digest-an-algorithm-for-computing-approximate-quantiles-on-a-collection-of-integers/
>>>
>>> So this is not about estimating population quantiles from a small
>>> sample (see Nick's hdquantile on SSC, e.g.). This is about finding
>>> approximate quantiles in large data.
>>>
>>> If the answer is simply random downsampling before taking quantiles, I
>>> would still appreciate some guidance on how heavily to downsample as a
>>> function of population size.
>>>
>>> Thanks!
>>>
>>> Laszlo
>>
>> *
>> *   For searches and help try:
>> *   http://www.stata.com/help.cgi?search
>> *   http://www.stata.com/support/faqs/resources/statalist-faq/
>> *   http://www.ats.ucla.edu/stat/stata/

*
*   For searches and help try:
*   http://www.stata.com/help.cgi?search
*   http://www.stata.com/support/faqs/resources/statalist-faq/
*   http://www.ats.ucla.edu/stat/stata/

*
*   For searches and help try:
*   http://www.stata.com/help.cgi?search
*   http://www.stata.com/support/faqs/resources/statalist-faq/
*   http://www.ats.ucla.edu/stat/stata/