Graduation Semester and Year
2018
Language
English
Document Type
Thesis
Degree Name
Master of Science in Computer Science
Department
Computer Science and Engineering
First Advisor
Song Jiang
Second Advisor
David Levine
Abstract
Trie or prefix tree is a data structure that has been used widely in some applications such as prefix-matching, auto-complete suggestions, and IP routing tables for a long time. What makes tries even more interesting is that its time complexity is dependent on the length of the keys inserted or searched in the trie, instead of on the total number of keys in the data structure. Tries are also strong contenders to consider against hash tables in various applications due to two reasons - their almost deterministic time complexity based on average key length, especially when using large number of short length keys, and support for range queries. IP routing table is one such example that chooses tries over hash tables. But even with all these benefits, tries have vlargely remained unused in a lot of potential candidate applications , for example in database indexing, due to their space consumption. The amount of pointers used in a trie causes its space consumption to be a lot more than many other data structures such as B+ Trees. Another issue we realized with tries is that even though the time complexity can be of a magnitude far less than some other data structures for short length keys, it can be considerably higher if the keys are of longer lengths. Insertion in a trie can prove to be a repetitive operation for many nodes if the keys are repetitive or have many common prefixes adding to the execution overhead. With this in mind, we propose two optimizations of the trie data structure to address the time and space complexity issues. In the first optimization we present a system that reduces the time for inserts in the trie data structure by up-to 50% for some workloads by tweaking the algorithm. In the second optimization we developed a new version of the trie data structure by taking inspiration from B+ trees, allowing us to not only reduce the space consumption for tries but also to allow features such as efficient range search.
Keywords
Trie, Prefix tree, Algorithms, B+ tree, Space, Time, Asymptotic
Disciplines
Computer Sciences | Physical Sciences and Mathematics
License
This work is licensed under a Creative Commons Attribution-NonCommercial-Share Alike 4.0 International License.
Recommended Citation
Kale, Nirmik Milind, "Improving time and space efficiency of trie data structure" (2018). Computer Science and Engineering Theses. 515.
https://mavmatrix.uta.edu/cse_theses/515
Comments
Degree granted by The University of Texas at Arlington