Indian Journal of Science and Technology

Abstract

Tree and Trie are the Abstract Data Types (ADTs) that provide efficient implementation of ordered dictionary. The performance of a data structure will depend on hardware capabilities of the computing devices such as RAM size, Cache memory size and even the speed of the physical storage media. Hence, an application which will be running on real or virtualized hardware environment certainly will have restricted access to memory and other resources of the real hardware. Further, the time taken for any operation on a data structure rely on the data usage model and the most significant operations/tests are very much depend on the size of the “character payload objects” which we use in dictionary like implementations. In this work, we do an analysis on the performance of Tree and Trie based Dictionary ADT Implementations with different data usage models. We consider data usage models such as a typical electronic dictionary with more than million of words or a typical electronic encyclopedia with large string data elements. In this work, we studied the performance of three popular Tree based Dictionary Implementations rbtree, googlebtree, stxbtree, and three Trie based Dictionary Implementations tommy-trie, tommy-trie-inplace, nedtrie under different hardware and software configurations. Among all, tommy trie is proved to be the best for character payload objects with 16 bytes and 4096 bytes. In some operations/tests googlebtree seems to be better. Our evaluation on different tree and trie structures shows tommy trie implementations perform well irrespective of size of application.

Keywords:
Cache, googlebtree, rbtree, stx btree, Tommy trie, Trie