TITLE:
Prime Box Parallel Search Algorithm: Searching Dynamic Dictionary in O(lg m) Time
AUTHORS:
Amit Pandey, Berhane Wolde-Gabriel, Elias Jarso
KEYWORDS:
Prime Box Search Algorithm, Information Retrieval, Lexicographical Search, Dynamic Dictionary Search, Parallel Search
JOURNAL NAME:
Journal of Computer and Communications,
Vol.4 No.4,
April
27,
2016
ABSTRACT: Hashing and Trie tree data structures are among the preeminent
data mining techniques considered for the ideal search. Hashing techniques have
the amortized time complexity of O(1). Although in worst case, searching a hash
table can take as much as θ(n) time [1]. On the other hand, Trie tree data
structure is also well renowned data structure. The ideal lookup time for
searching a string of length m in database of n strings using Trie data
structure is O(m) [2]. In the present study, we have proposed a novel Prime Box
parallel search algorithm for searching a string of length m in a dictionary of
dynamically increasing size, with a worst case search time complexity of
O(log2m). We have exploited parallel techniques over this novel algorithm to
achieve this search time complexity. Also this prime Box search is independent
of the total words present in the dictionary, which makes it more suitable for
dynamic dictionaries with increasing size.