DPSA: Deterministic Parallel Search Algorithm in Large Database

Abstract

The main goal of parallel processing is to reduce the complexity of finding a solution for a problem. In this study, we consider the problem of searching for multiple items at the same time in a large database. We propose a parallel search algorithm that reduces the searching time in comparison to binary search algorithm saving in that the time needed for sorting. Our algorithm works well for any data that can be represented in binary and it converts the searching of two items to search for a composed key that is the AND-combination of the two searched items. DPSA our proposed algorithm outperforms Binary search algorithm in searching for two items at the same time where the binary search will search them sequentially. The running time of our algorithm in the worst case is O(n) for searching two items in a data input of size n.