An efficient approach for mining top-K fault-tolerant repeating patterns

Jia Ling Koh, Yu Ting Kung

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

2 Citations (Scopus)

Abstract

In this paper, an efficient strategy for mining top-K non-trivial faulttolerant repeating patterns (FT-RPs in short) with lengths no less than min_len from data sequences is provided. By extending the idea of appearing bit sequences, fault-tolerant appearing bit sequences are defined to represent the locations where candidate patterns appear in a data sequence with insertion/deletion errors being allowed. Two algorithms, named TFTRP-Mine(Top-K non-trivial FT-RPs Mining) and RE-TFTRP-Mine (REfinement of TFTRP-Mine), respectively, are proposed. Both of these two algorithms use the recursive formulas to obtain the fault-tolerant appearing bit sequence of a pattern systematically and then the fault-tolerant frequency of each candidate pattern could be counted quickly. Besides, RE-TFTRP-Mine adopts two additional strategies for pruning the searching space in order to improve the mining efficiency. The experimental results show that RE-TFTRP-Mine outperforms TFTRP-Mine algorithm when K and min_len are small. In addition, more important and implicit repeating patterns could be found from real music objects by adopting fault tolerant mining.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - 11th International Conference, DASFAA 2006, Proceedings
Pages95-110
Number of pages16
DOIs
Publication statusPublished - 2006 Jul 7
Event11th International Conference on Database Systems for Advanced Applications, DASFAA 2006 - Singapore, Singapore
Duration: 2006 Apr 122006 Apr 15

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3882 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th International Conference on Database Systems for Advanced Applications, DASFAA 2006
CountrySingapore
CitySingapore
Period06/4/1206/4/15

Fingerprint

Fault-tolerant
Mining
Refinement
Recursive Formula
Pruning
Music
Deletion
Insertion
Experimental Results
Strategy

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Koh, J. L., & Kung, Y. T. (2006). An efficient approach for mining top-K fault-tolerant repeating patterns. In Database Systems for Advanced Applications - 11th International Conference, DASFAA 2006, Proceedings (pp. 95-110). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3882 LNCS). https://doi.org/10.1007/11733836_9

An efficient approach for mining top-K fault-tolerant repeating patterns. / Koh, Jia Ling; Kung, Yu Ting.

Database Systems for Advanced Applications - 11th International Conference, DASFAA 2006, Proceedings. 2006. p. 95-110 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3882 LNCS).

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

Koh, JL & Kung, YT 2006, An efficient approach for mining top-K fault-tolerant repeating patterns. in Database Systems for Advanced Applications - 11th International Conference, DASFAA 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3882 LNCS, pp. 95-110, 11th International Conference on Database Systems for Advanced Applications, DASFAA 2006, Singapore, Singapore, 06/4/12. https://doi.org/10.1007/11733836_9
Koh JL, Kung YT. An efficient approach for mining top-K fault-tolerant repeating patterns. In Database Systems for Advanced Applications - 11th International Conference, DASFAA 2006, Proceedings. 2006. p. 95-110. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11733836_9
Koh, Jia Ling ; Kung, Yu Ting. / An efficient approach for mining top-K fault-tolerant repeating patterns. Database Systems for Advanced Applications - 11th International Conference, DASFAA 2006, Proceedings. 2006. pp. 95-110 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{18233f3a908e4447943380e890692428,
title = "An efficient approach for mining top-K fault-tolerant repeating patterns",
abstract = "In this paper, an efficient strategy for mining top-K non-trivial faulttolerant repeating patterns (FT-RPs in short) with lengths no less than min_len from data sequences is provided. By extending the idea of appearing bit sequences, fault-tolerant appearing bit sequences are defined to represent the locations where candidate patterns appear in a data sequence with insertion/deletion errors being allowed. Two algorithms, named TFTRP-Mine(Top-K non-trivial FT-RPs Mining) and RE-TFTRP-Mine (REfinement of TFTRP-Mine), respectively, are proposed. Both of these two algorithms use the recursive formulas to obtain the fault-tolerant appearing bit sequence of a pattern systematically and then the fault-tolerant frequency of each candidate pattern could be counted quickly. Besides, RE-TFTRP-Mine adopts two additional strategies for pruning the searching space in order to improve the mining efficiency. The experimental results show that RE-TFTRP-Mine outperforms TFTRP-Mine algorithm when K and min_len are small. In addition, more important and implicit repeating patterns could be found from real music objects by adopting fault tolerant mining.",
author = "Koh, {Jia Ling} and Kung, {Yu Ting}",
year = "2006",
month = "7",
day = "7",
doi = "10.1007/11733836_9",
language = "English",
isbn = "3540333371",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "95--110",
booktitle = "Database Systems for Advanced Applications - 11th International Conference, DASFAA 2006, Proceedings",

}

TY - GEN

T1 - An efficient approach for mining top-K fault-tolerant repeating patterns

AU - Koh, Jia Ling

AU - Kung, Yu Ting

PY - 2006/7/7

Y1 - 2006/7/7

N2 - In this paper, an efficient strategy for mining top-K non-trivial faulttolerant repeating patterns (FT-RPs in short) with lengths no less than min_len from data sequences is provided. By extending the idea of appearing bit sequences, fault-tolerant appearing bit sequences are defined to represent the locations where candidate patterns appear in a data sequence with insertion/deletion errors being allowed. Two algorithms, named TFTRP-Mine(Top-K non-trivial FT-RPs Mining) and RE-TFTRP-Mine (REfinement of TFTRP-Mine), respectively, are proposed. Both of these two algorithms use the recursive formulas to obtain the fault-tolerant appearing bit sequence of a pattern systematically and then the fault-tolerant frequency of each candidate pattern could be counted quickly. Besides, RE-TFTRP-Mine adopts two additional strategies for pruning the searching space in order to improve the mining efficiency. The experimental results show that RE-TFTRP-Mine outperforms TFTRP-Mine algorithm when K and min_len are small. In addition, more important and implicit repeating patterns could be found from real music objects by adopting fault tolerant mining.

AB - In this paper, an efficient strategy for mining top-K non-trivial faulttolerant repeating patterns (FT-RPs in short) with lengths no less than min_len from data sequences is provided. By extending the idea of appearing bit sequences, fault-tolerant appearing bit sequences are defined to represent the locations where candidate patterns appear in a data sequence with insertion/deletion errors being allowed. Two algorithms, named TFTRP-Mine(Top-K non-trivial FT-RPs Mining) and RE-TFTRP-Mine (REfinement of TFTRP-Mine), respectively, are proposed. Both of these two algorithms use the recursive formulas to obtain the fault-tolerant appearing bit sequence of a pattern systematically and then the fault-tolerant frequency of each candidate pattern could be counted quickly. Besides, RE-TFTRP-Mine adopts two additional strategies for pruning the searching space in order to improve the mining efficiency. The experimental results show that RE-TFTRP-Mine outperforms TFTRP-Mine algorithm when K and min_len are small. In addition, more important and implicit repeating patterns could be found from real music objects by adopting fault tolerant mining.

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

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

U2 - 10.1007/11733836_9

DO - 10.1007/11733836_9

M3 - Conference contribution

AN - SCOPUS:33745534805

SN - 3540333371

SN - 9783540333371

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

SP - 95

EP - 110

BT - Database Systems for Advanced Applications - 11th International Conference, DASFAA 2006, Proceedings

ER -