Title: Some Algorithms for Parallel and Distributed Statistics

Speaker: Timothy B. Terriberry

Date/Time: Monday, November 24, 2008, 11:00 – 12:00 noon

Location: CSRI Building/Room 279 (Video-Conference presentation)

Brief Abstract: Formulas for incremental or parallel computation of second order central moments are well known. Together with Philippe Pébay, I have developed similar formulas for higher order moments, along with a generalized correction factor for two-pass algorithms. The first allows computation of higher order moments in a single pass or in parallel in distributed systems where communication costs are high. The second allows the standard two-pass algorithm to maintain accuracy over nearly the full representable range of the input, as demonstrated by experimental results. In addition, I discuss a new parallel algorithm for computing a "moment image", a generalization of parallel prefix sums to higher dimensions, and its implementation on a GPU. Once constructed, this allows the computation of statistical moments over arbitrary rectangular regions of an image in constant time.

CSRI POC: Brian Wylie, (505) 844-2238