Trie and Tree-Based Data Structures for Efficient String Searching

Read full text Summarise with VIRAT
Authors: Charan Sai Sree Kantipudi
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

This paper presents a comparative study of trie-based and tree-based data structures for efficient string searching, with applications in text processing, information retrieval, and database indexing. This paper analyzes standard tries, binary search trees, balanced trees, and suffix trees in terms of time complexity, space usage, and operational characteristics. This paper introduces a Hybrid Trie–Tree Index that stores the first k characters of each string in a trie and delegates the remaining suffix to a secondary container at depth k. This design reduces construction overhead while preserving efficient prefix-based navigation. Experimental evaluation is conducted on datasets of increasing scale, including a controlled 68-word vocabulary, a 200,000-word dataset, and a 1.5 million-word dataset. Results show that the hybrid structure achieves significantly faster build times compared to a standard trie, while search performance depends on the size of suffix containers. A parameter study varying the prefix depth k demonstrates a clear trade-off between construction efficiency and query latency. Smaller k values reduce build time but increase search overhead, while larger k values improve search performance at the cost of deeper trie expansion. These findings highlight the importance of tuning k based on dataset characteristics and application requirements.

Fields of Study & Subjects

Algorithms and Data Compression Advanced Database Systems and Queries Network Packet Processing and Optimization

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
25 March 2026
Language
EN
Document type
Preprint