Enhancement of Rabin-Karp Algorithm using XOR Filter

  • Beatrice A. Escoto BS Computer Science, Pamantasan ng Lungsod ng Maynila, Philippines
  • Acemon Jassene G. Ladines BS Computer Science, Pamantasan ng Lungsod ng Maynila, Philippines
  • Abigail Grace G. Macahilig BS Computer Science, Pamantasan ng Lungsod ng Maynila, Philippines
  • Mark Anthony S. Mercado Information Technology Department, Pamantasan ng Lungsod ng Maynila, Philippines
  • Dan Michael A. Cortez Computer Science Department, Pamantasan ng Lungsod ng Maynila, Philippines
  • Raymund M. Dioses Computer Science Department, Pamantasan ng Lungsod ng Maynila, Philippines
  • Jonathan C. Morano Computer Science Department, Pamantasan ng Lungsod ng Maynila, Philippines
  • Jamillah S. Guialil Computer Science Department, Pamantasan ng Lungsod ng Maynila, Philippines

Abstract

Purpose – The study aims to enhance the Rabin-Karp Algorithm that underlines the problem encountered wherein the algorithm’s runtime performance is affected due to the continuous rapid growth of data.

Method – Application of XOR Filter in the enhancement of the Rabin-Karp Algorithm is constructed to the given patterns to check for any pattern absences that will be removed from the data input. Then the updated patterns will be utilized in the string-matching process.

Results – The modified method displayed significant improvements in different input data sizes and patterns. After conducting runtime tests, it surpasses the improved algorithm using Bloom Filter by 9%, and a rate of 47.53% runtime performance compared to the traditional Rabin-Karp Algorithm.



Conclusion – The integration of the XOR Filter into the Rabin-Karp Algorithm, demonstrates a statistically significant runtime improvement. Moreover, it shows an effective scalability with larger datasets, proving its practical suitability for applications or scenarios that handle extensive datasets.

Recommendations – Future researchers are encouraged to explore other alternative techniques and the use of different filters that are not mentioned in this study. In addition, it extends future research on the use of Artificial Intelligence to explore diverse strategies and implementation for further improvement of the modified algorithm.

Research Implications – Potential directions for further research in string-matching algorithm optimization on effective integration of the XOR Filter into the Rabin-Karp Algorithm. Further highlighting the possibilities of using probabilistic data structures in algorithmic design are observed with the improvements in runtime efficiency. Data processing and pattern-matching areas open the door to effective and scalable solutions by promoting studies in the use of cutting-edge AI techniques to improve current algorithms.

Practical Implications – The Enhanced Rabin-Karp Algorithm can be used by Academic Institutions and Future Researchers to provide a more accurate string-matching process and improved runtime, supporting applications working with massive datasets.

Author Biographies

Beatrice A. Escoto, BS Computer Science, Pamantasan ng Lungsod ng Maynila, Philippines

Beatrice A. Escoto is an incoming graduate with a bachelor’s degree in computer science from Pamantasan ng Lungsod ng Maynila. She actively participates in tech-related extracurricular activities to gain exposure and enhance her skills. She is dedicated to developing her expertise in UI/UX Design and Quality Assurance, demonstrating strong leadership abilities. She interned at the university’s ICT Office, where she contributed as a mobile developer and analyst. In her free time, Beatrice enjoys visiting museums and reading tech articles, finding peace and inspiration in these activities.

Acemon Jassene G. Ladines, BS Computer Science, Pamantasan ng Lungsod ng Maynila, Philippines

Acemon Jassene G. Ladines is an aspiring backend developer from Pamantasan ng Lungsod ng Maynila, focusing on creating RESTful APIs. During an internship at the university's ICT Office, he honed his technical skills and gained practical experience. He is dedicated to continuous learning, upskilling on his own, and staying updated with the latest industry trends. Outside of his technical pursuits, Acemon enjoys watching series and working out, finding balance and relaxation through these activities.

Abigail Grace G. Macahilig, BS Computer Science, Pamantasan ng Lungsod ng Maynila, Philippines

Abigail Grace G. Macahilig, a driven student at Pamantasan ng Lungsod ng Maynila pursuing a Bachelor of Science in Computer Science. She is known for her unrelenting devotion to academic success, as well as a strong desire for ongoing learning and improvement. Throughout her undergraduate career, she distinguished herself through her continuous mastery of UI/UX design and Quality Assurance, demonstrating not only technical expertise but also an in-depth understanding of the symbiotic relationship between technology and human experience. Her professional experience includes an IT internship at Solid Shipping Lines Corporation, where she honed her skills in quality assurance and project management. Macahilig's journey is a testament to her passion for both learning and technological innovation.

Mark Anthony S. Mercado, Information Technology Department, Pamantasan ng Lungsod ng Maynila, Philippines

Professor Mark Anthony S. Mercado is an academic expert with information technology experience. After graduating from Arellano University with a Bachelor of Science in Computer Science with a Major in Information Technology and pursuing a Master's degree in Information Technology at the Technological University of the Philippines, he laid a solid foundation for his career. His dedication to lifelong learning and high standards in academia is apparent. His career in academia has been marked by a broad range of positions and responsibilities, including leadership positions as LMS Manager, Team Leader, and Subject Coordinator, as well as teaching positions at Arellano University and La Consolacion College Manila. Prof. Mercado's standing in the academic world was further cemented when he was appointed Chairperson of the Information Technology Department at Pamantasan ng Lungsod ng Maynila on August 17, 2023.

Dan Michael A. Cortez, Computer Science Department, Pamantasan ng Lungsod ng Maynila, Philippines

Dr. Dan Michael A. Cortez is the Vice President of Research, Academic, and Extension Services at the Pamantasan ng Lungsod ng Maynila. He previously held the position of Program Chairperson in the Computer Science Department. With ten years of teaching experience, he earned a Bachelor of Science in Information Technology and a Master of Science in Information and Communications Technology from the same institution. He earned his Doctorate Degree in Information Technology from the Technological Institute of the Philippines-Quezon City Campus. A member of PSITE-NCR and the Philippine Computing Society, as well as an author and researcher in information technology.

Raymund M. Dioses, Computer Science Department, Pamantasan ng Lungsod ng Maynila, Philippines

Raymund M. Dioses currently holds the positions of chairperson of the Computer Science Department and Assistant Professor I in the College of Information Systems and Technology Management. Before this, he spent eight years as a faculty member and chair of the Computer Education Department at CORE Gateway College Inc. and worked in the Senior High School Department of the Department of Education for five years. He holds a Master of Arts in Education, majoring in Educational Management from CORE Gateway College, and a Bachelor of Science in Computer Science from St. Jude College. At Nueva Ecija University of Science and Technology, he is also pursuing a Master of Information Technology, majoring in Computer Education. His vast background in academic administration and teaching has greatly improved his teaching abilities.

Jonathan C. Morano, Computer Science Department, Pamantasan ng Lungsod ng Maynila, Philippines

Jonathan C. Morano currently is a Lecturer I at Pamantasan ng Lungsod ng Maynila. He has more than 20 years of experience working and teaching in the field of Information Technology. Mr. Morano earned a Bachelor of Science in Computer Science from the Technological University of the Philippines. He acquired a Master of Arts in Teaching with a major in Information Technology from Central College of the Philippines, as well as a Master of Science in Information Technology from La Consolacion University Philippines. He is also the author of numerous research publications in information technology, both locally as well as internationally.

Jamillah S. Guialil, Computer Science Department, Pamantasan ng Lungsod ng Maynila, Philippines

Jamillah S. Guialil is a 27-year-old resident of Intramuros, Manila. She graduated with a Bachelor of Science in Computer Studies, majoring in Computer Science, in 2018. Currently, she is pursuing a Master of Information Technology at Pamantasan ng Lungsod ng Maynila. She also teaches as a part-time faculty member at the College of Information Systems and Technology Management at the same university. Her devotion to the field of technology is evident in her pursuit of excellence in both her studies and teaching.

Published
2024-08-10
How to Cite
ESCOTO, Beatrice A. et al. Enhancement of Rabin-Karp Algorithm using XOR Filter. International Journal of Computing Sciences Research, [S.l.], v. 8, p. 3088-3102, aug. 2024. ISSN 2546-115X. Available at: <//stepacademic.net/ijcsr/article/view/596>. Date accessed: 22 dec. 2024.
Citation Formats
Issue
Vol 8 (2024): Volume 8
Section
Articles

This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly credited.

Most read articles by the same author(s)