Structural Mapping for Recovering Missing Data Using the Aho-Corasick Algorithm
DOI:
https://doi.org/10.71229/r5m18w24Keywords:
Structural mapping, Aho-Corasick algorithm, missing data, pattern matching, data recoveryAbstract
This paper introduces a new structural mapping method to restore lost information based on the Aho-Corasick string-matching algorithm. The proposed approach uses techniques for pattern recognition and finite automata to identify and fill in missing segments in structured and semi-structured data such as HTML reports and biological sequences.
The basic idea consists in constructing a trie-based structure to perform multi-pattern matching using the known patterns extracted from the provided data. The use of suffix links in combination with a slightly modified greedy strategy have proven to correctly and easily restore missing information with low resource consumption.
Experimental results demonstrate that the method achieves a recovery rate of up to 97.3%, with a time complexity of O(m+n+k) , where m is the total length of all patterns, n is the input size, and k is the number of matches. This outperforms traditional approaches such as B-Trees, Hashing, and Binary Search in terms of both accuracy and efficiency.
This research also offers a new method known as Structural Tool for Automated Text (STOAT). The in-house tool was evaluated using both case studies at 10 MB and benchmarks at 10 GB in total comprising MIMIC-IV clinical notes, NCBI GenBank sequences, and Common Crawl web data. From the experiment, recovery is achieved between 87.1% and up to 97.3% with respect to the volume of data and missing rate.
In summary, this study extends the field of application of the Aho-Corasick algorithm beyond that of its traditional use, to the area of structural mapping for missing data recovery. Future work will consider generalization of the approach to unstructured text, including adaptation with machine learning for adaptive pattern detection and integration with real-time systems and secure data provenance frameworks.
References
1. Shadbahr, T., Roberts, M., Stanczuk, J., Gilbey, J., Teare, P., Dittmer, S., Thorpe, M., Viñas Torné, R., Sala, E., & Lió, P. (2023). The impact of imputation quality on machine learning classifiers for datasets with missing values. Communications Medicine, 3, Article 139. https://doi.org/10.1038/s43856-023-00356-z
2. Casella, M., Milano, N., Dolce, P., & Marocco, D. (2024). Transformers deep learning models for missing data imputation: An application of the ReMasker model on a psychometric scale. Frontiers in Psychology, 15, Article 1449272. https://doi.org/10.3389/fpsyg.2024.1449272
3. Fayez, M., Abbas, A., Khaled, H., & Ghoniemy, S. (2024). Enhanced Aho-Corasick algorithm for network intrusion detection systems. International Journal of Intelligent Computing and Information Sciences, 24(3), 83–92. https://doi.org/10.21608/ijicis.2024.315432.1349
4. Hu, Z., Hasegawa, H., Yamaguchi, Y., & Shimada, H. (2023). Realtime malicious traffic detection targeted for TCP out-of-order packets based on FPGA. IEEE Access, 11, 112212–112222. https://doi.org/10.1109/ACCESS.2023.3323853
5. Johnson, A. E. W., Bulgarelli, L., Shen, L., Gayles, A., Shammout, A., Horng, S., Pollard, T. J., Hao, S., Moody, B., Gow, B., Lehman, L. H., Celi, L. A., & Mark, R. G. (2023). MIMIC-IV, a freely accessible electronic health record dataset. Scientific Data, 10, Article 1. https://doi.org/10.1038/s41597-022-01899-x
6. Sayers, E. W., Cavanaugh, M., Clark, K., Pruitt, K. D., Sherry, S. T., Yankie, L., & Karsch-Mizrachi, I. (2024). GenBank 2024 update. Nucleic Acids Research. https://pubmed.ncbi.nlm.nih.gov/37889039/
7. Kwon, Y., Lee, S., Nam, Y., Na, J. C., Park, K., Cha, S. K., & Moon, B. (2023). DB+-tree: A new variant of B+-tree for main-memory database systems. Information Systems, 119, Article 102287.
8. Graefe, G. (2024). More modern B-tree techniques. Foundations and Trends in Databases, 13(3), 169–249.
9. Zhang, C., Zhou, L., Xiao, X., & Xu, D. (2023). A missing traffic data imputation method based on a diffusion convolutional neural network–generative adversarial network. Sensors, 23(23), Article 9601. https://doi.org/10.3390/s23239601
10. Leger, P., Fukuda, H., Cardozo, N., & Martín, D. S. (2024). Exploring a self-replication algorithm to flexibly match patterns. IEEE Access, 12, 13553–13570.
11. Khan, J., Rubel, T., Molloy, E., Dhulipala, L., & Patro, R. (2024). Fast, parallel, and cache-friendly suffix array construction. Algorithms for Molecular Biology, 19.
12. Pereira, R. C., Abreu, P. H., Rodrigues, P. P., & Figueiredo, M. A. T. (2024). Imputation of data missing not at random: Artificial generation and benchmark analysis. Expert Systems with Applications, 249, Article 123654.
13. Prakash, P., Street, K., Narayanan, S., Fernandez, B. A., Shen, Y., & Shu, C. (2024). Benchmarking machine learning missing data imputation methods in large-scale mental health survey databases. medRxiv. https://doi.org/10.1101/2024.05.13.24307231
14. Ou, H., Yao, Y., & He, Y. (2024). Missing data imputation method combining random forest and generative adversarial imputation network. Sensors, 24(4), Article 1112. https://doi.org/10.3390/s24041112
15. Paterakis, G., Fafalios, S., Charonyktakis, P., Christophides, V., & Tsamardinos, I. (2024). Do we really need imputation in AutoML predictive modeling? ACM Transactions on Knowledge Discovery from Data.
16. Kowsar, I., Rabbani, S. B., & Samad, M. D. (2024). Attention-based imputation of missing values in electronic health records tabular data. In Proceedings of the 2024 IEEE 12th International Conference on Healthcare Informatics (ICHI) (pp. 177–182). IEEE. https://doi.org/10.1109/ICHI61247.2024.00030
17. Varzaneh, Z. A., & Hosseini, S. (2024). An improved equilibrium optimization algorithm for feature selection problem in network intrusion detection. Scientific Reports, 14, Article 67488. https://doi.org/10.1038/s41598-024-67488-7
18. Huang, W., Tian, H., Wang, S., Zhang, C., & Zhang, X. (2024). Integration of simulated annealing into pigeon inspired optimizer algorithm for feature selection in network intrusion detection systems. PeerJ Computer Science. https://doi.org/10.7717/peerj-cs.2176
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Al-Noor Journal of Engineering Management and Computer Science
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
How to Cite
