Improving time and space efficiency of trie data structure
View/ Open
Date
2018-08-15Author
Kale, Nirmik Milind
0000-0001-7455-0089
Metadata
Show full item recordAbstract
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.