Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | FAQ
 
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2014, Vol. 29 Issue (5) :740-750    DOI: 10.1007/s11390-014-1464-3
Artificial Intelligence and Pattern Recognition Current Issue | Archive | Adv Search << Previous Articles | Next Articles >>
Pattern Matching with Flexible Wildcards
Xindong Wu1(吴信东), Fellow, IEEE, Ji-Peng Qiang1(强继朋), Fei Xie1,3(谢飞)
1. Department of Computer Science, Hefei University of Technology, Hefei 230009, China;
2. Department of Computer Science, University of Vermont, Burlington, VT 05405, U. S. A. ;
3. Department of Computer Science and Technology, Hefei Normal University, Hefei 230601, China

Abstract
Reference
Related Articles
Download: [PDF 445KB]     Export: BibTeX or EndNote (RIS)  
Abstract Pattern matching with wildcards (PMW) has great theoretical and practical significance in bioinformatics, information retrieval, and pattern mining. Due to the uncertainty of wildcards, not only the number of all matches is exponential with respect to the maximal gap flexibility and the pattern length, but the matching positions in PMW are also hard to choose. The objective to count the maximal number of matches one by one is computationally infeasible. Therefore, rather than solving the generic PMW problem, many research efforts have further defined new problems within PMW according to different application backgrounds. To break through the limitations of either fixing the number or allowing an unbounded number of wildcards, pattern matching with flexible wildcards (PMFW) allows the users to control the ranges of wildcards. In this paper, we provide a survey on the state-of-the-art algorithms for PMFW, with detailed analyses and comparisons, and discuss challenges and opportunities in PMFW research and applications
Articles by authors
Xindong Wu
Ji-Peng Qiang
Fei Xie
Keywordspattern matching   wildcards   bioinformatics   pattern mining     
Received 2014-02-17;
Fund:

This paper is supported in part by the National Natural Science Foundation of China under Grant Nos. 61229301 and 60828005, the Program for Changjiang Scholars and Innovative Research Team in University (PCSIRT) of the Ministry of Education, China, under Grant No. IRT13059, and the National Science Foundation (NSF) of USA under Grant No. 0514819.

About author: Xindong Wu is a Yangtze RiverScholar in the School of Computer Science and Information Engineering at the Hefei University of Technology, China, a professor of computer science at the University of Vermont, USA, and a fellow of IEEE and AAAS. He received his B.S. and M.S. degrees in computer science from the Hefei University of Technology, China, and his Ph.D. degree in artificial intelligence from the University of Edinburgh, Britain. His research interests include data mining, big data analytics, knowledgebased systems, and Web information exploration. He is currently the steering committee chair of the IEEE International Conference on Data Mining (ICDM), the editorin-chief of Knowledge and Information Systems (KAIS, by Springer), and a series editor-in-chief of the Springer Book Series on Advanced Information and Knowledge Processing (AI & KP). He was the editor-in-chief of the IEEE Transactions on Knowledge and Data Engineering (TKDE, by the IEEE Computer Society) between 2005 and 2008. He served as program committee chair/co-chair for the 2003 IEEE International Conference on Data Mining, the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, and the 19th ACM Conference on Information and Knowledge Management.
Cite this article:   
Xindong Wu, Ji-Peng Qiang, Fei Xie.Pattern Matching with Flexible Wildcards[J]  Journal of Computer Science and Technology, 2014,V29(5): 740-750
URL:  
http://jcst.ict.ac.cn:8080/jcst/EN/10.1007/s11390-014-1464-3
Copyright 2010 by Journal of Computer Science and Technology