[prev in list] [next in list] [prev in thread] [next in thread] 

List:       monetdb-developers
Subject:    Re: [Monetdb-developers] Fastest way to calculate median?
From:       Marcin Zukowski <Marcin.Zukowski () cwi ! nl>
Date:       2008-06-09 12:12:35
Message-ID: 484D1E33.5080003 () cwi ! nl
[Download RAW message or body]

> Hi - I have an int column with several million rows of data.  What is the fastest way to write a query to get the median value of the column?  Apparently there is no median() function in SQL.  A web search revealed lots of various talk about using stored procedures and fancy functions.  None of this looked like it would be very efficient.  I searched these archives but didn't see a single mention of median.  Thank you!
I'm not an expert on MonetDB/SQL, but finding a median (on any quantile) is a 
well researched problem, e.g. http://en.wikipedia.org/wiki/Selection_algorithm
Still, MEDIAN is a significantly different function than e.g. SUM or AVG, 
that's why it's usually not supported in SQL.

You have some choices:
1. sort and select, e.g. :
   SELECT value FROM table ORDER BY value LIMIT half_table_size, 1.
This probably has an O(NlogN) complexity, might be acceptable for your data 
sizes. I hope MonetDB/SQL supports LIMIT ;)
2. use binary search, also O(NlogN), a bit more complicated
3. use Hoere's algorithm (quickselect), which can generate the answer in O(N) 
(average case), but it requires some explicit data manipulation. Only worth it 
if you really focus on speed.

I'd go for #1, if it's too slow, I'd try #3

Good luck,
m.


> 
> 
> 
>       
> 
> 
> -------------------------------------------------------------------------
> Check out the new SourceForge.net Marketplace.
> It's the best place to buy or sell services for
> just about anything Open Source.
> http://sourceforge.net/services/buy/index.php
> _______________________________________________
> Monetdb-developers mailing list
> Monetdb-developers@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/monetdb-developers

-- 
: Marcin Zukowski < marcin@cwi.nl | http://www.cwi.nl/~marcin >

-------------------------------------------------------------------------
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Monetdb-developers mailing list
Monetdb-developers@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/monetdb-developers
[prev in list] [next in list] [prev in thread] [next in thread]