The data preprocessing is helpful in removing noise, inconsistency in the given data and produce quality data. The output of the data preprocessing is then given to refinement of existing algorithm that can later applied over the data structures called external sorting, optimal binary search trees, and pattern matching algorithms. In external sorting(first case), user data entered can be qualified using Data preprocessing, then separate algorithms used to different data items such as numeric and alphabets. In Optimal binary search trees (second case), user entered data can be made quality data using data preprocessing (second case), then refined algorithm used over the data elements that produce OBSTs separately for numeric items, and String items. In pattern matching (third case), user entered data can be made quality data, then refined algorithm used over the text which immediately finds out index for the pattern along with history of indices for the substring which further helpful in manual identification of the given pattern in the large given text. The results and graphs were also demonstrated based on certain examples. This also differentiates between time complexities obtained of the existing and proposed algorithm used over the data structures such as external sorting, OBST, and pattern matching.

Data preprocessing, data structures, external sorting, Optimal Binary Search Trees, Pattern Matching, Time Complexities

[1] Mark Allen Weiss, �Data Structures and Algorithm Analysis in C++�, Fourth Edition, Chapter7, Page No (297 � 347).
[2] Mark Allen Weiss, �Data Structures and Algorithm Analysis in Java� , Third Edition, Chapter7, Page No (297 � 347).
[3] Alfred V. Aho, John E. HopCroft and Jelfrey D. Ullman, �Data Structures and Algorithms�, Sorting, Addison �Wesley, 1983.
[4] Micheline Kamber and Jiawei Han, �Data Mining Principles and Techniques�, Data Preprocessing, Morgan Kaufmann, 2006, Page No (13 -30)
[5] Margaret H Dunham, �Data Mining Introductory and Advanced Topics�, Pearson Education, 3e, 2008
[6] Sam Anahory and Dennis Murray, �Data Ware housing in the Real World�, Pearson Education, 2003
[7] D. E. Knuth (1985), �The Art of Computer Programming�, Sorting and Searching, Vol. 3, Addison �Wesley, Reading, MA, 1985
[8] Alok Aggarwal, Jeffrey Scott Vitter, �Algorithms and Data Structures�, Input and Output Complexity of Sorting and related problems, AV88.pdf.
[9] Leu, Fang-Cheng; Tsai, Yin-Te; Tang, Chuan Yi, �An efficient External Sorting Algorithm�, pp (159-163), Information Processing Letters 75 2000.
[10] Ian H. Witten, Eibe Frank, Morgan Kaufmann, �Data Mining: Practical Machine Learning Tools and Techniques�, Second Edition (Morgan Kaufmann Series in Data Management Systems), 2005.
[11] Zhi � Hua Zhou, Dept. of CSE, Nanjing University , �Introduction to Data Mining�, part3: Data Preprocessing, Spring 2012, Pt03.pdf.
[12] Chiara Rebso, �Introduction to Data Mining: Data Preprocessing�, KDD- LAB, ISTI � CNR, Pisa, Italy.
[13] Michael T.Good Rich, Roberto Tamassia,�Data Structures and Algorithms in java�,6th Edition.
[14] Akepogu Ananda Rao, Radhika Raju Palagiri, �Data Structures and Algorithms using C++ �.
[15] Donald Adjeroh, Timothy Bell, Amar Mukharjee, �The Burrows Wheeler Transform�.
[16] Machael McMillan,� Data Structures and Algorithms using Visual Basic.NET�.
[17] Svetlana, Eden,�Introduction to String Matching and modification in R using Regular expressions�, march,2007.
[18] Jeffrey.E.F.Fredl, �Mastering Regular Expression� , 3rd Edition, 3rd Edition, O,reilly publications.
[19] �Regular expressions and Matching in Modern Perl�, 2011-12 edition.
[20] S. S. Sheik,Sumit K. Aggarwal, Anindya Poddar, N. Balakrishnan, K. Sekar,.,�A FAST Pattern Matching Algorithm�, J. Chem Inf. Comput. Sci. 2004, 44, 1251-1256.
[21] Micheline Kamber, Jiawei Han, � Data Mining Concepts and Techniques�, Second Edition.
[22] Dorian Pyle, �Data preparation for Data Mining�, Morgan Kaufmann Publishers, Inc.
[23] Pang-Ning Tan, Vipin Kumar, Michael Steenbach, �Introduction to Data Mining�, Addition-Wesley Companion book site, Page No (19 � 88).
[24] E.Horotiwz, S.Sahni, Dinesh Mehta, �Fundamentals of data structures in C++� , Second Edition.