Received: from golem.jpl.nasa.gov (IDENT:postfix@dialin-068.jpl.nasa.gov [128.149.231.68]) by hub.org (8.10.1/8.10.1) with ESMTP id e6J26uh92917 for ; Tue, 18 Jul 2000 22:06:57 -0400 (EDT) Received: from alumni.caltech.edu (localhost.localdomain [127.0.0.1]) by golem.jpl.nasa.gov (Postfix) with ESMTP id 651E06F52; Wed, 19 Jul 2000 02:12:35 +0000 (UTC) Message-ID: <39750E93.D7D9517E@alumni.caltech.edu> Date: Wed, 19 Jul 2000 02:12:35 +0000 From: Thomas Lockhart Organization: Yes X-Mailer: Mozilla 4.7 [en] (X11; I; Linux 2.2.14-15mdksmp i686) X-Accept-Language: en MIME-Version: 1.0 To: Jan Wieck Cc: omid omoomi , BKermani@illumina.com, pgsql-sql@postgresql.org Subject: Re: Median References: <200007181935.VAA12101@hot.jw.home> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Archive-Number: 200007/180 > 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