首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:Prime Box Parallel Search Algorithm: Searching Dynamic Dictionary in O(lg m) Time
  • 本地全文:下载
  • 作者:Amit Pandey ; Berhane Wolde-Gabriel ; Elias Jarso
  • 期刊名称:Journal of Computer and Communications
  • 印刷版ISSN:2327-5219
  • 电子版ISSN:2327-5227
  • 出版年度:2016
  • 卷号:04
  • 期号:04
  • 页码:134-145
  • DOI:10.4236/jcc.2016.44012
  • 语种:English
  • 出版社:Scientific Research Publishing
  • 摘要: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.
  • 关键词:Prime Box Search Algorithm;Information Retrieval;Lexicographical Search;Dynamic Dictionary Search;Parallel Search
国家哲学社会科学文献中心版权所有