title: Block-suffix shifting: fast, simultaneous medical concept set identification in large medical record corpora.
abstract: Owing to new advances in computer hardware, large text databases have become more prevalent than ever.Automatically mining information from these databases proves to be a challenge due to slow pattern/string matching techniques. In this paper we present a new, fast multi-string pattern matching method based on the well known Aho-Chorasick algorithm. Advantages of our algorithm include:the ability to exploit the natural structure of text, the ability to perform significant character shifting, avoiding backtracking jumps that are not useful, efficiency in terms of matching time and avoiding the typical "sub-string" false positive errors.Our algorithm is applicable to many fields with free text, such as the health care domain and the scientific document field. In this paper, we apply the BSS algorithm to health care data and mine hundreds of thousands of medical concepts from a large Electronic Medical Record (EMR) corpora simultaneously and efficiently. Experimental results show the superiority of our algorithm when compared with the top of the line multi-string matching algorithms.
authors.affiliation: College of IST, The Pennsylvania State University, University Park, PA, USA.
authors.forename: Ying
authors.initials: Y
authors.lastname: Liu
authors.forename: Lucian Vlad
authors.initials: LV
authors.lastname: Lita
authors.forename: Radu Stefan
authors.initials: RS
authors.lastname: Niculescu
authors.forename: Prasenjit
authors.initials: P
authors.lastname: Mitra
authors.forename: C Lee
authors.initials: CL
authors.lastname: Giles
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D016247:Information Storage and Retrieval / Q000379:methods*; D016347:Medical Records Systems, Computerized; D009323:Natural Language Processing; D010363:Pattern Recognition, Automated / Q000379:methods*; D009626:Terminology as Topic