[Pig-user] Percentile UDF

HI all,

Does anybody have a UDF for calculating the percentile (median, 99%) at all?
I took a look at the builtins
and the piggybank project, but couldn't seem to see anything. Is there a
reason why there isn't a builtin for
this?

Many thanks,
Jon.

I think it would be because there's an inherently serial problem in
there (i.e. numbering each entry based on its place in the ordered
list).

Cheers,
Kris

Hey Jon,

I wrote one not long ago that just relies on Apache Commons Math underlying
the UDF. It's pretty straightforward as the Percentile implementation will
sort your numbers before doing percentile calculations. The UDF then just
needs to take a bag/tuple, pull out all the fields as double[] and pass into
Percentile.

http://commons.apache.org/math/apidocs/org/apache/commons/math/stat/descriptive/rank/Percentile.html

Josh

You can get an approximated percentile without completely ordering the list.

Caveat: Assuming your values have a small distribution. You can use
rounding to shrink the distribution.

In SQL terms. 'select value as val,count(1) as count from X group by
value order by value'

This should result in a small result set with very large counts. Get
the total count. You can now find the percentile of this smaller list.

Hey Josh,

That's the path I started down today, I don't suppose the UDF you wrote is
in the public domain
at all - would you consider contributing it to piggybank.jar at all? How
does it fare with large datasets
as well?

Many thanks,
Jon.

This was my attempt at the Percentile function today:

http://pastebin.com/C883rwbJ

Any tips on improving the efficiency of it would be welcome. Dmitriy
mentioned using a histogram as an approach for this and looking at the way
GROUP BY works. If anybody has any further info on that approach I'd be
interested in hearing about it.

Cheers,
Jon.

1) change log.info to log.debug... you don't want that spamming your logs
for a billion tuples.
2) instanceof DefaultDataBag should probably be instanceof DataBag (other
databags are ok too)
3) the somewhat more scalable version of this would group by value (or value
range, for histograms) and provide a series of (value, numentries) pairs --
assuming numentries tends to be above 2, you can get substantial savings in
terms of memory there
4) if you use an ArrayList instead of an array, you don't need to
precalculate the size of the bag. But then a copy to array is required for
Percentile to work. So you can implement your own Percentile that wouldn't
require you to triple-buffer...

D

Jon,

I haven't tried with any super large DataBags but would definitely pursue
Dmitriy's grouping suggestion if memory usage/size is of concern and you
have a very large distribution. Something I will have to try as well!

Cheers,

Josh

It's not very clear how you are doing this in a single eval func efficiently, or are you scanning all the tuples within a single invocation of the eval func?

For this to be scalable and O(n), wouldn't you need at least 2 map-reduce jobs? The first job to calculate histograms (which can be scaled up by the map phase assigning buckets in parallel) and the reduce computing the counts for each bucket; the second job to calculate the percentile rank of each tuple in a map phase using the histograms (which again can be done in parallel).

-----Original Message-----
From: joshdevins@gmail.com On Behalf Of Josh Devins
Sent: 12 March 2011 04:36
To: user@pig.apache.org
Cc: Dmitriy Ryaboy; Jonathan Holloway
Subject: Re: Percentile UDF

Jon,

I haven't tried with any super large DataBags but would definitely pursue Dmitriy's grouping suggestion if memory usage/size is of concern and you have a very large distribution. Something I will have to try as well!

Cheers,

Josh