Re: Median - Mailing list pgsql-sql

From Thomas Lockhart
Subject Re: Median
Date
Msg-id 39750E93.D7D9517E@alumni.caltech.edu
Whole thread Raw
In response to Re: Median  (JanWieck@t-online.de (Jan Wieck))
List pgsql-sql
> Maybe someone else has an idea.

I implemented a different algorithm several years ago. It is an
O(log(N)) process (unlike most other techniques), and was borrowed from
the "Algorithms" book (it's at work; but it is the classic "yellow
jacket" book with Fortran code and the other volume with *really bad* C
code which looks like Fortran ;)

Anyway, once the bugs were fixed (and there were several :( and a better
endgame algorithm was coded, it was suitable for hypercube distributed
processing, where you just exchange a small amount of info between
iterations. And it involved simply *counting* how many values were above
and below an initial or updated guess, then iterating on a new guess.

afaik that wouldn't be suitable for the existing aggregate capabilities,
but multi-pass algorithms would be nice to be able to do.
                   - Thomas


pgsql-sql by date:

Previous
From: andrew
Date:
Subject: Re: using a self referencing table
Next
From: Patrick Coulombe
Date:
Subject: out-subject : thanks