Extracting Frequent Subsequences from a Single Long Data Sequence: A Novel Anti-Monotonic Measure and a Simple On-Line Algorithm Koji Iwanuma, Ryuichi Ishihara, Yo Takano, and Hidetomo Nabeshima   View Paper (PDF)   Return to Session 7: Time Series III Abstract In this paper, we study frequent-subsequence extraction from a single very-long data-sequence. First we propose a novel frequency measure, called the total frequency, for counting multiple occurrences of a sequential pattern in a single data sequence. The total frequency is anti-monotonic, and makes it possible to count up pattern occurrences without duplication. Moreover the total frequency has a good property for implementation based on the dynamic programming strategy. Second we give a simple on-line algorithm for a specialized subsequence extraction problem, i.e., a problem with the infinite window-length. This specialized problem is considered to be a relaxation of the general-case problem, thus this fast on-line algorithm is important from the view of practical applications. ©2006 Association for Computing Machinery