Window-chained longest common subsequence: Common event matching in sequences
Chunyao Song, Tingjian Ge · 2015
Sequence data is prevalent, and event processing over sequences is increasingly important in this Big Data era, drawing much attention from both research and industry. In this paper, we address a novel problem, which is to find common event subsequences from two long sequences. This problem is well motivated, with applications in diverse domains. We propose the window-chained longest common subsequence (WCLCS) semantics, and argue that the traditional longest common subsequence (LCS) cannot serve this need. We then devise efficient algorithms to solve this problem by reducing it to a graph problem. We also propose two more methods to improve the performance: one is based on informed search and exploration, and the other is an approximation algorithm with accuracy guarantees. We finally carry out a systematic experimental evaluation using two real-world datasets and some synthetic datasets.