Data Analysis Through Segmentation: Bayesian Blocks and Beyond
J.D. Scargle (NASA Ames Research Center)

This tutorial covers analysis methods for detecting and
characterizing structure in time series data, based on
optimal segmentation of the observational interval. Examples
include cases where the fitness function to be optimized is
the Bayesian posterior for the full piece-wise constant
model of the data, yielding the {\it Bayesian Blocks}
representation. For any fitness function a novel dynamic
programming algorithm finds the global optimum partition,
over all possible partitions of the interval (an
exponentially large search space!) in time proportional to
the square of the number of data points.

This methodology has been extended to 2D data (e.g. images
or photon maps), 3D data (e.g. from redshift surveys), and
data of higher dimension. These problems can be solved by
transformation first into finite combinatorial
optimizations, and then into equivalent one dimensional
problems that can be solved with the 1D algorithm discussed
above.

The tutorial itself, plus descriptions of MatLab
implementations of the algorithms and sample applications,
will be made available electronically. I gratefully
acknowledge support from the NASA Applied Information System
Research Program, the Intelligent Systems Program, and the
NASA Ames Director's Discretionary Fund.