1
$\begingroup$

You are given two things: A fixed initial 'model' partition of an interval, e.g.

I------I---I-----I-------I----...

where each - or I represents an element in a discrete time series and the Is are the partition boundaries. This can also be represented as a sequence of subinterval lengths, i.e. 7, 4, 6, 8, ...

Then, you're given a new set of subinterval lengths; and the task is to arrange these in such a way as to get as many coincident Is as possible. Or equivalently, you are given a new partition on an interval of the same length (though, critically, the new partition may have greater or fewer elements) and the task is to shuffle the subintervals around to maximize alignment. So if the model was

I------I---I-----I-------I----I

and you are given 2, 11, 5, 12, i.e.

I-I----------I----I-----------I

then the solution would be 11, 2, 12, 5,

I----------I-I-----------I----I
           *             *

achieving alignment at 2 locations (marked with an asterisk, compare to model).

There is an additional constraint: The locations of the aligned subintervals must be distributed approximately randomly throughout the length of the solution. The simplest means of getting a partition with at least some alignment to the model would be to build the new partition segment by segment, drawing without replacement from the collection of test segments, aligning where possible. But this would strongly bias the occurrences of alignment towards the beginning of the time series, and is therefore not allowed. There is of course also the brute force O(n!) enumeration but my series are little too long for that.

Naturally a solution that finds the optimal permutation would be great, but one that is efficient and gets a permutation with a substantial fraction of the possible alignment would also be good. My current version is a variation on the 'simple' algorithm derived above, except only drawing from a small subcollection of subintervals so as to avoid bias. I know it can be improved upon!

$\endgroup$
  • $\begingroup$ the subproblem of alignment with 2 coincidences looks similar to subset-sum (find $k$ subintervals from the second partition whose summed lengths equal the distance between 2 markers taken from the first partition), so i wouldn't expect an efficient solution. moreover, the vector of the alignment lengths affects the randomness of the location distribution. take as an extreme case a sequence of partitions who support $k$ alignments of the same length $l$ where the partition is of length($kl$): there is no randomness at all. whats your tradeoff between location randomness alignment count? $\endgroup$ – collapsar Apr 3 '14 at 13:47
  • $\begingroup$ @collapsar Thanks for your tip on the subset-sum problem. Indeed, an efficient optimal solution may be out of reach. As for the extreme case, insofar as non-randomness is somehow dictated by the structure of the model, then that's not a problem. The important thing is that the algorithm itself should not itself add any bias. By 'random' I just mean 'random relative to the distribution of possible coincidences, given the model'. $\endgroup$ – Matt Phillips Apr 3 '14 at 14:22
  • $\begingroup$ Is this a practical problem? What are the typical parameters? i.e., how long is the interval, and how many elements are there in the partition (typically)? About how many locations do you expect it'll typically be possible to align? (i.e., typically just 2, or many more?) Are you fine with a heuristic algorithm that works well in practice, or are you looking for something with a worst-case running time that can be proven? This looks like a good candidate to solve with ILP or with SAT. $\endgroup$ – D.W. Apr 3 '14 at 23:23
  • 1
    $\begingroup$ @D.W. Yes, this is very much a practical problem. The interval is 1000-2000 samples long though I would like the solution to work for longer lengths. My current attempts can get about 40% coincidence. The test partitions will have on average the same number of subintervals but that can vary by 50-200%. I am perfectly fine with a heuristic algorithm. Good q., I am not worried about worst-case scenario, something that is fast on average. The model is generated from a gamma distribution so it will not be 'pathological'. $\endgroup$ – Matt Phillips Apr 4 '14 at 1:30
2
$\begingroup$

You can use integer linear programming (ILP) to solve this. In particular, here is how to use an ILP solver to test whether there exists a way to permute the second partition so that you find $k+1$ alignment points (including the two endpoints). Given an algorithm for this decision procedure, you can use binary search to find the optimal alignment.

Call a "block" the (non-empty) sequence of consecutive intervals between two alignment points. The left and right endpoint of the interval are automatically alignment points. If there are $k+1$ distinct alignment points (including these two endpoints), there will be $k$ blocks.

Let $\ell_1,\ell_2,\dots,\ell_n$ be the set of lengths of the first set of subintervals, and $\ell^*_1,\ell^*_2,\dots,\ell^*_{n^*}$ be the lengths of the second set of subintervals. These are constants provided as input.

Introduce zero-or-one unknowns $x_{i,j}$ (for $1\le i\le n$ and $1 \le j \le k$), with the intent that $x_{i,j}=1$ means that the $i$th subinterval (of length $\ell_i$) from the first partition will end up in the $j$th block. Similarly, introduce zero-or-one unknowns $x^*_{i,j}$, with the intent that $x^*_{i,j}$ means that the $i$th subinterval (of length $\ell^*_i$) from the second partition will end up in the $j$th block.

Now we get a set of linear inequalities, as follows:

  • $\sum_i \ell_i x_{i,j} = \sum_i \ell^*_i x^*_{i,j}$, for all $j$. (This is two ways of representing the length of the $j$th block.)

  • $\sum_j x_{i,j} = 1$ (each subinterval from the first partition ends up in exactly one block) and $\sum_j x^*_{i,j} = 1$.

  • $x_{i,j} = 1 \land x_{i+1,j}=0 \implies x_{i+1,j+1} = 1$ (i.e., each block starts where the previous one ended). This can be expressed as the ILP constraint $x_{i,j} - x_{i+1,j} \le x_{i+1,j+1}$. Similarly for the $x^*$'s.

  • $x_{i,j} = 1 \land x_{i'',j} = 1 \land i < i' < i'' \implies x_{i',j}=1$ (i.e., the subintervals in a block are consecutive). This can be expressed as the ILP constraint $x_{i,j} + x_{i'',j} - 1 \le x_{i',j}$ for all $i,i',i''$ with $i < i' < i''$. Similarly for the $x^*$'s.

  • $x_{1,1} = 1$, $x^*_{1,1} = 1$, $x_{n,k}=1$, $x^*_{n^*,k}=1$.

Of course, in the worst case ILP can take exponential time, but ILP solvers are pretty good and often perform well on many real-world problems, so it is probably worth a try.

(You could also try coding this up using a SAT solver, but you'd need to implement arithmetic, so a front-end like STP would probably be a better bet than a plain SAT solver.)

$\endgroup$
  • $\begingroup$ Hi, I've found Gurobi for linear programming, but not 'STP', despite googling--can you unpack the acronym or give me a link? Thank you-- $\endgroup$ – Matt Phillips Apr 8 '14 at 20:10
  • $\begingroup$ This approach is cool. I'm starting to learn about LP. What am I trying to maximize in this case though? I would have thought $k$, but that doesn't seem to be what you have in mind. Also I note that I have $\ell^*_1, ... \ell^*_m$, $m \neq n$ in general, but I don't think that changes anything. $\endgroup$ – Matt Phillips Apr 8 '14 at 21:22
  • 1
    $\begingroup$ For the LP version: you're not trying to maximize anything, you're just checking feasibility. (You can do that by asking the solver to maximize some arbitrary sum of some of the variables, it doesn't matter what; all you care is whether the solver says Feasible or Infeasible.) As for STP: sites.google.com/site/stpfastprover $\endgroup$ – D.W. Apr 9 '14 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.