File Based Trie for Embedded Devices

Huge volume, variance and velocity of data due to digitalization of various sectors have lead to information explosion. Storing and retrieval of huge volume of data requires appropriate data structures that will contribute towards performance optimization of the computing systems. Trie and its variants are popular in applications ranging from sub-string search to auto completion, where strings are used as keys. Trie data structure is characterised by huge memory requirements, thus it is infeasible to store in primary memory, especially for embedded devices where memory is a constraint, thus implementing a trie in secondary storage is a feasible solution for embedded devices. B tree, B+ trees, B trie and Burst trie are reported data structures that are designed to minimize read and write latency in secondary memory. We propose a File-based trie that performs insert, search and delete operations without explicitly loading trie data into the primary memory. We compare the performance of File-based Linked list-trie with B trie, B trees and FlatBuffers on strings form standard dictionary. Our results demonstrate that Linked list-trie takes 40 percent less lookup time compared to B trie, B tree and 29 percent less lookup time compared to FlatBuffers. Linked list-trie consumes 7 KB of main memory and provide support for characters of multiple languages. The implementation can be further investigated for applications involving query completion, prefix matching etc.