Fast sequence segmentation using log-linear models

Title: Fast sequence segmentation using log-linear models

Abstract:
Sequence segmentation is a well-studied classic problem, where given a sequence of
elements, an integer K, and some measure of homogeneity, the task is to split
the sequence into K contiguous segments that are maximally homogenous.  A
classic approach to find the optimal solution is by using a dynamic program.
Unfortunately, the execution time of this program is quadratic w.r.t the length
of the input sequence. This makes the algorithm slow for a sequence of
non-trivial length.

We demonstrate that if we are dealing with one-dimensional sequences, then
we can significantly speed-up the dynamic program. While the
worst-case time and space complexity is still the same as with original program,
in practice the speed-up is significant and the time complexity is closer to linear than to quadratic.

Bio:
Dr. Nikolaj Tatti is a postdoctoral research at Aalto University / Finnish Centre of Excellence for Algorithmic Data Analysis Research (Algodan).
Prior to that Dr. Tatti was a postdoctoral fellow (FWO) at University of Antwerp and KU Leuven, Belgium. Dr. Tatti received his PhD from Helsinki
University of Technology in 2008. Dr. Tatti's research interests include statistically sound pattern mining and efficient algorithms in knowledge discovery.