Tracking maximum ascending subsequences in sequences of partially ordered data

Abstract

We consider scenarios in which long sequences of data are analyzed and subsequences must be traced that are monotone and maximum, according to some measure. A classical example is the online Longest Increasing Subsequence Problem for numeric and alphanumeric data. We extend the problem in two ways: (a) we allow data from any partially ordered set, and (b) we maximize subsequences using much more general measures than just length or weight. Let P be a poset of finite width w, and let δ be any data sequence over P. We show that the measure of the maximum monotone subsequences in δ can be maintained in at most O(w log min( n w , Dn)) time and O(min(n, wDn)) memory when the n-th data item is processed, where Dn is the ‘depth’ of the measure at position n (n ≥ 1). The result generalizes all earlier O(log n) time-per-input results for the corresponding longest or heaviest increasing subsequence problems.