|
|
 |
|
Mercredi 4 Décembre
| Heure: |
10:30 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
A New Approach to String Pattern Mining with Approximate Match |
| Description: |
Uno Takeaki Frequent string mining is the problem of finding frequently appearingstrings in a given string database or large text.It has many applications to string data analysis on strings such as texts,word sequences, and genome sequences.The problem becomes difficult if the string patterns are allowed to matchapproximately, i.e., a fixed number of errors leads to an explosionin the number of small solutions, and a fixed ratio of errors violatesthe monotonicity that disables hill climbing algorithms, and thusmakes searching difficult.There would be also a difficulty on the modeling of the problem;simple mathematical definitions would result explosion of the solutions.To solve this difficulty, we go back to the motivations to find frequentstrings, and propose a new method for generating string patternsthat appear in the input string many times.In the method, we first compute the similarity between the stringsin the database, and enumerate clusters generated by similarity.We then compute representative strings for each cluster, and therepresentatives are our frequent strings.Further, by taking majority votes, we extend the obtained representativesto obtain long frequent strings.The computational experiments we performed show the efficiency of bothour model and algorithm; we were able to find many stringpatterns appearing many times in the data, and that were long butnot particularly numerous.The computation time of our method is practically short, such as20 minutes even for a genomic sequence of 100 millions of letters. |
|
|
