Parallel processing can be harmful: The unusual behavior of interpolation search
It is known that the interpolation search algorithm for retrieving a key in an ordered array of N entries has expected running time O(log log(N)) when the array entries and the key searched for are generated by the uniform distribution over the (0,1) interval. In fact the expected running time is bounded by log log(N)\(+O(1).\) The impact of parallel processing on this problem is investigated. The results indicate that parallel processing for this problem is not very helpful. If P processors are available an evident improvement on the standard interpolation algorithm, called VARIATION(P) in the paper, is obtained which performs standard interpolation search up to the stage where the remaining segment of the array consists of at most P entries, at which stage these P entries are searched in parallel by the P processors. From the known analysis of the interpolation search algorithm it follows that VARIATION(P) has an expected running time log log(N)-log log(P)\(+O(1)\). The surprising result is that this trivial algorithm represents the optimal way of using P processors. No algorithm which uses P processors can improve on the number of stage by more than an additive constant; moreover, if the communication overhead caused by the need of the processors to exchange information is accounted for by any multiplicative constant \(c>1\) the resulting expected case running time will exceed the running time of the almost sequential algorithm VARIATION(P). The proofs in the paper are based on the techniques in earlier papers by \textit{A. C. Yao} and \textit{F. F. Yao}; probabilistic estimates on Bernoulli trials provide the required estimates that with high probability the length of the array segment still under consideration is reduced by a square root; when P processors are used the size of this segment becomes a factor P smaller, but in the iteration the total gain of these factors P remains a constant.
- An algorithmic and complexity analysis of interpolation search
- Design and implementation of an efficient priority queue
- scientific article; zbMATH DE number 3909753 (Why is no real title available?)
- scientific article; zbMATH DE number 3919834 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3493681 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- scientific article; zbMATH DE number 3299217 (Why is no real title available?)
- Interpolation search—a log log N search
- Log-logarithmic worst-case range queries are possible in space theta(N)
- New trie data structures which support very fast search operations
- On the Number of Successes in Independent Trials
- Understanding the complexity of interpolation search
- Interpolation-binary search
- Effect of data organization in a system of interleaved memories on the performance of parallel search
- A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time
- Coefficients of speedup and parallel effectiveness of the parallel searching method
- scientific article; zbMATH DE number 3860406 (Why is no real title available?)
This page was built for publication: Parallel processing can be harmful: The unusual behavior of interpolation search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1825662)
