Longest Increasing Subsequence Computation over Streaming Sequences.

In this paper, we propose a data structure, a quadruple neighbor list (QN-list, for short), to support real time queries of all <underline>l</underline>ongest <underline>i</underline>ncreasing <underline>s</underline>ubsequence (LIS) and LIS with constraints over sequential data streams. The QN-List built by our algorithm requires $O(w)$<alternatives> <inline-graphic xlink:href="zou-ieq1-2761345.gif"/></alternatives> space, where $w$<alternatives><inline-graphic xlink:href="zou-ieq2-2761345.gif"/> </alternatives> is the time window size. The running time for building the initial QN-List takes $O(w\ \log w)$<alternatives><inline-graphic xlink:href="zou-ieq3-2761345.gif"/></alternatives> time. Applying the QN-List, insertion of the new item takes $O(\log w)$ <alternatives><inline-graphic xlink:href="zou-ieq4-2761345.gif"/></alternatives> time and deletion of the first item takes $O(w)$<alternatives> <inline-graphic xlink:href="zou-ieq5-2761345.gif"/></alternatives> time. To the best of our knowledge, this is the first work to support both LIS enumeration and LIS with constraints computation by using a single uniform data structure for real time sequential data streams. Our method outperforms the state-of-the-art methods in both time and space cost, not only theoretically, but also empirically. [ABSTRACT FROM PUBLISHER]