Finding best patterns practically

Ayumi Shinohara; Masayuki Takeda; Setsuo Arikawa; Masahiro Hirao; Hiromasa Hoshino; Shunsuke Inenaga

doi:10.1007/3-540-45884-0_21

Finding best patterns practically

Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Masahiro Hirao, Hiromasa Hoshino, Shunsuke Inenaga

INF - System Information Sciences

Kyushu University

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

11 Citations (Scopus)

Abstract

Finding a pattern which separates two sets is a critical task in discovery. Given two sets of strings, consider the problem to find a subsequence that is common to one set but never appears in the other set. The problem is known to be NP-complete. Episode pattern is a generalized concept of subsequence pattern where the length of substring containing the subsequence is bounded. We generalize these problems to optimization problems, and give practical algorithms to solve them exactly. Our algorithms utilize some pruning heuristics based on the combinatorial properties of strings, and efficient data structures which recognize subsequence and episode patterns.

Original language	English
Title of host publication	Progress in Discovery Science
Publisher	Springer Verlag
Pages	307-317
Number of pages	11
ISBN (Print)	3540433384, 9783540433385
DOIs	https://doi.org/10.1007/3-540-45884-0_21
Publication status	Published - 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2281
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/3-540-45884-0_21

Cite this

Shinohara, A., Takeda, M., Arikawa, S., Hirao, M., Hoshino, H., & Inenaga, S. (2002). Finding best patterns practically. In Progress in Discovery Science (pp. 307-317). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2281). Springer Verlag. https://doi.org/10.1007/3-540-45884-0_21

@inbook{5e634c0a8e7049509ee31b5e9a5167f2,

title = "Finding best patterns practically",

abstract = "Finding a pattern which separates two sets is a critical task in discovery. Given two sets of strings, consider the problem to find a subsequence that is common to one set but never appears in the other set. The problem is known to be NP-complete. Episode pattern is a generalized concept of subsequence pattern where the length of substring containing the subsequence is bounded. We generalize these problems to optimization problems, and give practical algorithms to solve them exactly. Our algorithms utilize some pruning heuristics based on the combinatorial properties of strings, and efficient data structures which recognize subsequence and episode patterns.",

author = "Ayumi Shinohara and Masayuki Takeda and Setsuo Arikawa and Masahiro Hirao and Hiromasa Hoshino and Shunsuke Inenaga",

year = "2002",

doi = "10.1007/3-540-45884-0_21",

language = "English",

isbn = "3540433384",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "307--317",

booktitle = "Progress in Discovery Science",

address = "Germany",

}

Finding best patterns practically. / Shinohara, Ayumi; Takeda, Masayuki; Arikawa, Setsuo et al.
Progress in Discovery Science. Springer Verlag, 2002. p. 307-317 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2281).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

TY - CHAP

T1 - Finding best patterns practically

AU - Shinohara, Ayumi

AU - Takeda, Masayuki

AU - Arikawa, Setsuo

AU - Hirao, Masahiro

AU - Hoshino, Hiromasa

AU - Inenaga, Shunsuke

PY - 2002

Y1 - 2002

N2 - Finding a pattern which separates two sets is a critical task in discovery. Given two sets of strings, consider the problem to find a subsequence that is common to one set but never appears in the other set. The problem is known to be NP-complete. Episode pattern is a generalized concept of subsequence pattern where the length of substring containing the subsequence is bounded. We generalize these problems to optimization problems, and give practical algorithms to solve them exactly. Our algorithms utilize some pruning heuristics based on the combinatorial properties of strings, and efficient data structures which recognize subsequence and episode patterns.

AB - Finding a pattern which separates two sets is a critical task in discovery. Given two sets of strings, consider the problem to find a subsequence that is common to one set but never appears in the other set. The problem is known to be NP-complete. Episode pattern is a generalized concept of subsequence pattern where the length of substring containing the subsequence is bounded. We generalize these problems to optimization problems, and give practical algorithms to solve them exactly. Our algorithms utilize some pruning heuristics based on the combinatorial properties of strings, and efficient data structures which recognize subsequence and episode patterns.

UR - http://www.scopus.com/inward/record.url?scp=23044534938&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=23044534938&partnerID=8YFLogxK

U2 - 10.1007/3-540-45884-0_21

DO - 10.1007/3-540-45884-0_21

M3 - Chapter

AN - SCOPUS:23044534938

SN - 3540433384

SN - 9783540433385

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 307

EP - 317

BT - Progress in Discovery Science

PB - Springer Verlag

ER -

Finding best patterns practically

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this