IncSpan: Incremental mining of sequential patterns in large database

Hong Cheng; Xifeng Yan; Jiawei Han

IncSpan: Incremental mining of sequential patterns in large database

Hong Cheng, Xifeng Yan, Jiawei Han

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Many real life sequence databases grow incrementally. It is undesirable to mine sequential patterns from scratch each time when a small set of sequences grow, or when some new sequences are added into the database. Incremental algorithm should be developed for sequential pattern mining so that mining can be adapted to incremental database updates. However, it is nontrivial to mine sequential patterns incrementally, especially when the existing sequences grow incrementally because such growth may lead to the generation of many new patterns due to the interactions of the growing subsequences with the original ones. In this study, we develop an efficient algorithm, IncSpan, for incremental mining of sequential patterns, by exploring some interesting properties. Our performance study shows that IncSpan outperforms some previously proposed incremental algorithms as well as a non-incremental one with a wide margin.

Original language	English (US)
Title of host publication	KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Editors	R. Kohavi, J. Gehrke, W. DuMouchel, J. Ghosh
Pages	527-532
Number of pages	6
State	Published - 2004
Event	KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - Seattle, WA, United States Duration: Aug 22 2004 → Aug 25 2004

Publication series

Name	KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Other

Other	KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Country/Territory	United States
City	Seattle, WA
Period	8/22/04 → 8/25/04

Keywords

Buffering pattern
Incremental mining
Reverse pattern matching
Shared projection

ASJC Scopus subject areas

General Engineering

Library availability

Discover UIUC Full Text

Cite this

Cheng, H., Yan, X., & Han, J. (2004). IncSpan: Incremental mining of sequential patterns in large database. In R. Kohavi, J. Gehrke, W. DuMouchel, & J. Ghosh (Eds.), KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 527-532). (KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

IncSpan: Incremental mining of sequential patterns in large database. / Cheng, Hong; Yan, Xifeng; Han, Jiawei.
KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ed. / R. Kohavi; J. Gehrke; W. DuMouchel; J. Ghosh. 2004. p. 527-532 (KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Cheng, H, Yan, X & Han, J 2004, IncSpan: Incremental mining of sequential patterns in large database. in R Kohavi, J Gehrke, W DuMouchel & J Ghosh (eds), KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 527-532, KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Seattle, WA, United States, 8/22/04.

Cheng H, Yan X, Han J. IncSpan: Incremental mining of sequential patterns in large database. In Kohavi R, Gehrke J, DuMouchel W, Ghosh J, editors, KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2004. p. 527-532. (KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

Cheng, Hong ; Yan, Xifeng ; Han, Jiawei. / IncSpan : Incremental mining of sequential patterns in large database. KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. editor / R. Kohavi ; J. Gehrke ; W. DuMouchel ; J. Ghosh. 2004. pp. 527-532 (KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining).

@inproceedings{c7ff83eb4ff9498fa77bdc6d3431b65d,

title = "IncSpan: Incremental mining of sequential patterns in large database",

abstract = "Many real life sequence databases grow incrementally. It is undesirable to mine sequential patterns from scratch each time when a small set of sequences grow, or when some new sequences are added into the database. Incremental algorithm should be developed for sequential pattern mining so that mining can be adapted to incremental database updates. However, it is nontrivial to mine sequential patterns incrementally, especially when the existing sequences grow incrementally because such growth may lead to the generation of many new patterns due to the interactions of the growing subsequences with the original ones. In this study, we develop an efficient algorithm, IncSpan, for incremental mining of sequential patterns, by exploring some interesting properties. Our performance study shows that IncSpan outperforms some previously proposed incremental algorithms as well as a non-incremental one with a wide margin.",

keywords = "Buffering pattern, Incremental mining, Reverse pattern matching, Shared projection",

author = "Hong Cheng and Xifeng Yan and Jiawei Han",

year = "2004",

language = "English (US)",

isbn = "1581138881",

series = "KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

pages = "527--532",

editor = "R. Kohavi and J. Gehrke and W. DuMouchel and J. Ghosh",

booktitle = "KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",

note = "KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ; Conference date: 22-08-2004 Through 25-08-2004",

}

TY - GEN

T1 - IncSpan

T2 - KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

AU - Cheng, Hong

AU - Yan, Xifeng

AU - Han, Jiawei

PY - 2004

Y1 - 2004

N2 - Many real life sequence databases grow incrementally. It is undesirable to mine sequential patterns from scratch each time when a small set of sequences grow, or when some new sequences are added into the database. Incremental algorithm should be developed for sequential pattern mining so that mining can be adapted to incremental database updates. However, it is nontrivial to mine sequential patterns incrementally, especially when the existing sequences grow incrementally because such growth may lead to the generation of many new patterns due to the interactions of the growing subsequences with the original ones. In this study, we develop an efficient algorithm, IncSpan, for incremental mining of sequential patterns, by exploring some interesting properties. Our performance study shows that IncSpan outperforms some previously proposed incremental algorithms as well as a non-incremental one with a wide margin.

AB - Many real life sequence databases grow incrementally. It is undesirable to mine sequential patterns from scratch each time when a small set of sequences grow, or when some new sequences are added into the database. Incremental algorithm should be developed for sequential pattern mining so that mining can be adapted to incremental database updates. However, it is nontrivial to mine sequential patterns incrementally, especially when the existing sequences grow incrementally because such growth may lead to the generation of many new patterns due to the interactions of the growing subsequences with the original ones. In this study, we develop an efficient algorithm, IncSpan, for incremental mining of sequential patterns, by exploring some interesting properties. Our performance study shows that IncSpan outperforms some previously proposed incremental algorithms as well as a non-incremental one with a wide margin.

KW - Buffering pattern

KW - Incremental mining

KW - Reverse pattern matching

KW - Shared projection

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

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

M3 - Conference contribution

AN - SCOPUS:12244291514

SN - 1581138881

SN - 9781581138887

T3 - KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP - 527

EP - 532

BT - KDD-2004 - Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

A2 - Kohavi, R.

A2 - Gehrke, J.

A2 - DuMouchel, W.

A2 - Ghosh, J.

Y2 - 22 August 2004 through 25 August 2004

ER -

IncSpan: Incremental mining of sequential patterns in large database

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Library availability

Related links

Fingerprint

Cite this