KP-Trie Algorithm for Update and Search Operations
Feras Hanandeh1, Izzat
Alsmadi2, Mohammed Akour3, and Essam Al Daoud4
1Department of Computer Information
Systems, Hashemite University, Jordan
2, 3Department of Computer Information Systems, Yarmouk University, Jordan
4Computer Science Department, Zarqa University, Jordan
Abstract: Radix-Tree is a space optimized data structure that performs data
compression by means of cluster nodes that share the same branch. Each node
with only one child is merged with its child and is considered as space
optimized. Nevertheless, it can’t be considered as speed optimized because the
root is associated with the empty string. Moreover, values are not
normally associated with every node; they are associated only with leaves and
some inner nodes that correspond to keys of interest. Therefore, it takes time
in moving bit by bit to reach the desired word. In this paper we propose the
KP-Trie which is consider as speed and space optimized data structure that is
resulted from both horizontal and vertical compression.
Keywords: Trie, radix tree, data structure, branch factor,
indexing, tree structure, information retrieval.
Received January 14, 2015;
accepted March 23, 2015; Published online
December 23, 2015