Enhancement of Rabin-Karp Algorithm using XOR Filter - Escoto, Beatrice A.; Ladines, Acemon Jassene G.; Macahilig, Abigail Grace G.; Mercado, Mark Anthony S.; Cortez, Dan Michael A.; Dioses, Raymund M.; Morano, Jonathan C.; Guialil, Jamillah S. (International Journal of Computing Sciences Research, 2024)
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.