Efficient Discovery of Frequent Approximate Sequential Patterns

We propose an efficient algorithm for mining frequent approximate sequential patterns under the Hamming distance model. Our algorithm gains its efficiency by adopting a "break-down-and-build-up" methodology. The "breakdown" is based on the observation that all occurrences of a fr...

Full description

Saved in:
Bibliographic Details
Main Authors: ZHU, Feida, YAN, Xifeng, HAN, Jiawei, YU, Philip S.
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2007
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/933
https://ink.library.smu.edu.sg/context/sis_research/article/1932/viewcontent/EfficientDiscoveryFrequentAppSeqPatterns_2007.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-1932
record_format dspace
spelling sg-smu-ink.sis_research-19322017-11-22T05:58:29Z Efficient Discovery of Frequent Approximate Sequential Patterns ZHU, Feida YAN, Xifeng HAN, Jiawei YU, Philip S. We propose an efficient algorithm for mining frequent approximate sequential patterns under the Hamming distance model. Our algorithm gains its efficiency by adopting a "break-down-and-build-up" methodology. The "breakdown" is based on the observation that all occurrences of a frequent pattern can be classified into groups, which we call strands. We developed efficient algorithms to quickly mine out all strands by iterative growth. In the "build-up" stage, these strands are grouped up to form the support sets from which all approximate patterns would be identified. A salient feature of our algorithm is its ability to grow the frequent patterns by iteratively assembling building blocks of significant sizes in a local search fashion. By avoiding incremental growth and global search, we achieve greater efficiency without losing the completeness of the mining result. Our experimental studies demonstrate that our algorithm is efficient in mining globally repeating approximate sequential patterns that would have been missed by existing methods. 2007-10-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/933 info:doi/10.1109/ICDM.2007.75 https://ink.library.smu.edu.sg/context/sis_research/article/1932/viewcontent/EfficientDiscoveryFrequentAppSeqPatterns_2007.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Hamming distance model Hamming distance model approximate sequential patterns break-down-and-build-up methodology frequent approximate sequential patterns global search incremental growth Databases and Information Systems Numerical Analysis and Scientific Computing
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Hamming distance model
Hamming distance model
approximate sequential patterns
break-down-and-build-up methodology
frequent approximate sequential patterns
global search
incremental growth
Databases and Information Systems
Numerical Analysis and Scientific Computing
spellingShingle Hamming distance model
Hamming distance model
approximate sequential patterns
break-down-and-build-up methodology
frequent approximate sequential patterns
global search
incremental growth
Databases and Information Systems
Numerical Analysis and Scientific Computing
ZHU, Feida
YAN, Xifeng
HAN, Jiawei
YU, Philip S.
Efficient Discovery of Frequent Approximate Sequential Patterns
description We propose an efficient algorithm for mining frequent approximate sequential patterns under the Hamming distance model. Our algorithm gains its efficiency by adopting a "break-down-and-build-up" methodology. The "breakdown" is based on the observation that all occurrences of a frequent pattern can be classified into groups, which we call strands. We developed efficient algorithms to quickly mine out all strands by iterative growth. In the "build-up" stage, these strands are grouped up to form the support sets from which all approximate patterns would be identified. A salient feature of our algorithm is its ability to grow the frequent patterns by iteratively assembling building blocks of significant sizes in a local search fashion. By avoiding incremental growth and global search, we achieve greater efficiency without losing the completeness of the mining result. Our experimental studies demonstrate that our algorithm is efficient in mining globally repeating approximate sequential patterns that would have been missed by existing methods.
format text
author ZHU, Feida
YAN, Xifeng
HAN, Jiawei
YU, Philip S.
author_facet ZHU, Feida
YAN, Xifeng
HAN, Jiawei
YU, Philip S.
author_sort ZHU, Feida
title Efficient Discovery of Frequent Approximate Sequential Patterns
title_short Efficient Discovery of Frequent Approximate Sequential Patterns
title_full Efficient Discovery of Frequent Approximate Sequential Patterns
title_fullStr Efficient Discovery of Frequent Approximate Sequential Patterns
title_full_unstemmed Efficient Discovery of Frequent Approximate Sequential Patterns
title_sort efficient discovery of frequent approximate sequential patterns
publisher Institutional Knowledge at Singapore Management University
publishDate 2007
url https://ink.library.smu.edu.sg/sis_research/933
https://ink.library.smu.edu.sg/context/sis_research/article/1932/viewcontent/EfficientDiscoveryFrequentAppSeqPatterns_2007.pdf
_version_ 1770570775978311680