Signature pattern covering via local greedy algorithm and Pattern Shrink

Hyungsul Kim, Sungjin Im, Tarek Abdelzaher, Jiawei Han, David Sheridan, Shobha Vasudevan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Pattern mining is a fundamental problem that has a wide range of applications. In this paper, we study the problem of finding a minimum set of signature patterns that explain all data. In the problem, we are given objects where each object has an itemset and a label. A pattern is called a signature pattern if all objects with the pattern have the same label. This problem has many interesting applications such as assertion mining in hardware design and identifying failure causes from various log data. We show that the previous pattern mining methods are not suitable for mining signature patterns and identify the problems. Then we propose a novel pattern enumeration method which we call Pattern Shrink. Our method is strongly coupled with another novel method that is very similar to finding a local optimum with a negligible loss in performance. Our proposed methods show a speedup of more than ten times over the previous methods. Our methods are flexible enough to be extended to mining high confidence patterns, instead of signature patterns.

Original languageEnglish (US)
Title of host publicationProceedings - 11th IEEE International Conference on Data Mining, ICDM 2011
Pages330-339
Number of pages10
DOIs
StatePublished - Dec 1 2011
Event11th IEEE International Conference on Data Mining, ICDM 2011 - Vancouver, BC, Canada
Duration: Dec 11 2011Dec 14 2011

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786

Other

Other11th IEEE International Conference on Data Mining, ICDM 2011
CountryCanada
CityVancouver, BC
Period12/11/1112/14/11

Fingerprint

Labels
Hardware

Keywords

  • Local greedy algorithm
  • Pattern covering
  • Set covering
  • Signature mining

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Kim, H., Im, S., Abdelzaher, T., Han, J., Sheridan, D., & Vasudevan, S. (2011). Signature pattern covering via local greedy algorithm and Pattern Shrink. In Proceedings - 11th IEEE International Conference on Data Mining, ICDM 2011 (pp. 330-339). [6137237] (Proceedings - IEEE International Conference on Data Mining, ICDM). https://doi.org/10.1109/ICDM.2011.131

Signature pattern covering via local greedy algorithm and Pattern Shrink. / Kim, Hyungsul; Im, Sungjin; Abdelzaher, Tarek; Han, Jiawei; Sheridan, David; Vasudevan, Shobha.

Proceedings - 11th IEEE International Conference on Data Mining, ICDM 2011. 2011. p. 330-339 6137237 (Proceedings - IEEE International Conference on Data Mining, ICDM).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Kim, H, Im, S, Abdelzaher, T, Han, J, Sheridan, D & Vasudevan, S 2011, Signature pattern covering via local greedy algorithm and Pattern Shrink. in Proceedings - 11th IEEE International Conference on Data Mining, ICDM 2011., 6137237, Proceedings - IEEE International Conference on Data Mining, ICDM, pp. 330-339, 11th IEEE International Conference on Data Mining, ICDM 2011, Vancouver, BC, Canada, 12/11/11. https://doi.org/10.1109/ICDM.2011.131
Kim H, Im S, Abdelzaher T, Han J, Sheridan D, Vasudevan S. Signature pattern covering via local greedy algorithm and Pattern Shrink. In Proceedings - 11th IEEE International Conference on Data Mining, ICDM 2011. 2011. p. 330-339. 6137237. (Proceedings - IEEE International Conference on Data Mining, ICDM). https://doi.org/10.1109/ICDM.2011.131
Kim, Hyungsul ; Im, Sungjin ; Abdelzaher, Tarek ; Han, Jiawei ; Sheridan, David ; Vasudevan, Shobha. / Signature pattern covering via local greedy algorithm and Pattern Shrink. Proceedings - 11th IEEE International Conference on Data Mining, ICDM 2011. 2011. pp. 330-339 (Proceedings - IEEE International Conference on Data Mining, ICDM).
@inproceedings{9228ee8602f04a9998c1b7a34c7658ac,
title = "Signature pattern covering via local greedy algorithm and Pattern Shrink",
abstract = "Pattern mining is a fundamental problem that has a wide range of applications. In this paper, we study the problem of finding a minimum set of signature patterns that explain all data. In the problem, we are given objects where each object has an itemset and a label. A pattern is called a signature pattern if all objects with the pattern have the same label. This problem has many interesting applications such as assertion mining in hardware design and identifying failure causes from various log data. We show that the previous pattern mining methods are not suitable for mining signature patterns and identify the problems. Then we propose a novel pattern enumeration method which we call Pattern Shrink. Our method is strongly coupled with another novel method that is very similar to finding a local optimum with a negligible loss in performance. Our proposed methods show a speedup of more than ten times over the previous methods. Our methods are flexible enough to be extended to mining high confidence patterns, instead of signature patterns.",
keywords = "Local greedy algorithm, Pattern covering, Set covering, Signature mining",
author = "Hyungsul Kim and Sungjin Im and Tarek Abdelzaher and Jiawei Han and David Sheridan and Shobha Vasudevan",
year = "2011",
month = "12",
day = "1",
doi = "10.1109/ICDM.2011.131",
language = "English (US)",
isbn = "9780769544083",
series = "Proceedings - IEEE International Conference on Data Mining, ICDM",
pages = "330--339",
booktitle = "Proceedings - 11th IEEE International Conference on Data Mining, ICDM 2011",

}

TY - GEN

T1 - Signature pattern covering via local greedy algorithm and Pattern Shrink

AU - Kim, Hyungsul

AU - Im, Sungjin

AU - Abdelzaher, Tarek

AU - Han, Jiawei

AU - Sheridan, David

AU - Vasudevan, Shobha

PY - 2011/12/1

Y1 - 2011/12/1

N2 - Pattern mining is a fundamental problem that has a wide range of applications. In this paper, we study the problem of finding a minimum set of signature patterns that explain all data. In the problem, we are given objects where each object has an itemset and a label. A pattern is called a signature pattern if all objects with the pattern have the same label. This problem has many interesting applications such as assertion mining in hardware design and identifying failure causes from various log data. We show that the previous pattern mining methods are not suitable for mining signature patterns and identify the problems. Then we propose a novel pattern enumeration method which we call Pattern Shrink. Our method is strongly coupled with another novel method that is very similar to finding a local optimum with a negligible loss in performance. Our proposed methods show a speedup of more than ten times over the previous methods. Our methods are flexible enough to be extended to mining high confidence patterns, instead of signature patterns.

AB - Pattern mining is a fundamental problem that has a wide range of applications. In this paper, we study the problem of finding a minimum set of signature patterns that explain all data. In the problem, we are given objects where each object has an itemset and a label. A pattern is called a signature pattern if all objects with the pattern have the same label. This problem has many interesting applications such as assertion mining in hardware design and identifying failure causes from various log data. We show that the previous pattern mining methods are not suitable for mining signature patterns and identify the problems. Then we propose a novel pattern enumeration method which we call Pattern Shrink. Our method is strongly coupled with another novel method that is very similar to finding a local optimum with a negligible loss in performance. Our proposed methods show a speedup of more than ten times over the previous methods. Our methods are flexible enough to be extended to mining high confidence patterns, instead of signature patterns.

KW - Local greedy algorithm

KW - Pattern covering

KW - Set covering

KW - Signature mining

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

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

U2 - 10.1109/ICDM.2011.131

DO - 10.1109/ICDM.2011.131

M3 - Conference contribution

SN - 9780769544083

T3 - Proceedings - IEEE International Conference on Data Mining, ICDM

SP - 330

EP - 339

BT - Proceedings - 11th IEEE International Conference on Data Mining, ICDM 2011

ER -