Title: Fast sequence segmentation using log-linear models
Authors: Tatti, Nikolaj # ×
Issue Date: 2013
Publisher: Kluwer Academic Publishers
Series Title: Data Mining and Knowledge Discovery vol:27 issue:3 pages:421 -441
Abstract: Sequence segmentation is a well-studied 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 homogeneous. A
classic approach to find the optimal solution is by using a dynamic program.
Unfortunately, the execution time of this program is quadratic with respect to the length
of the input sequence. This makes the algorithm slow for a sequence of
non-trivial length. In this paper we study segmentations whose measure of
goodness is based on log-linear models, a rich family that contains many of the
standard distributions. We present a theoretical result allowing us to prune
many suboptimal segmentations. Using this result, we modify the standard
dynamic program for one-dimensional log-linear models, and by doing so reduce
the computational time. We demonstrate empirically, that this approach can
significantly reduce the computational burden of finding the optimal
ISSN: 1384-5810
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
paper.pdfOA article Published 407KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science