Performance Evaluation of a Hybrid Trie and Levenshtein Distance Search Architecture Compared to Various Search Algorithms

Abstract

Information retrieval in search systems frequently struggles to achieve both rapid query response times and robust error tolerance simultaneously. While numerous search algorithms are available, there is a lack of comparative studies evaluating their performance in balancing these two critical aspects. Among the available options, an opportunity exists to combine the Trie data structure and the Levenshtein Distance algorithm. Trie excels in computational speed, whereas Levenshtein Distance provides superior error tolerance. Leveraging these respective strengths creates an opportunity to merge both approaches to enhance overall search performance. Therefore, this study aims to propose and evaluate a hybrid search architecture that integrates Trie with Levenshtein Distance. An experimental quantitative methodology was conducted to evaluate eight different search algorithms. Performance was measured based on runtime execution and robustness metrics using a dataset of 3,000 book titles to simulate various typographical error scenarios. The evaluation process was automated using Python scripts, executing 30 iterations per query to ensure statistical validity. The results demonstrate that the proposed hybrid Trie and Levenshtein Distance achieves an average execution time of (4.324 ms). This performance is approximately 17.6 times faster than the native Levenshtein Distance (76.25 ms) and 34.6 times faster than the Damerau-Levenshtein Distance (149.73 ms). However, in terms of robustness, the hybrid approach did not show a significant improvement over the native fuzzy algorithms, as it successfully maintained the exact same level of error tolerance. The Trie structure effectively accelerates the search by pruning the search space, while Levenshtein Distance maintains flexibility in handling user input errors. In conclusion, this hybrid architecture provides a highly efficient and robust solution for autocomplete search features, successfully balancing computational speed with user-friendly error tolerance.