Parallel processing can be harmful: The unusual behavior of interpolation search

DOI10.1016/0890-5401(89)90038-2MaRDI QIDQ1825662zbMATH OpenOpenAlexFDO

Authors Dan E. Willard, J. Reif

Publication date 1989

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(89)90038-2

zbMATH Keywords

parallel algorithmsexpected case time analysisinterpolation sort

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Interpolation-binary search
• On Parallel Searching
• Dynamic interpolation search in \(o(\log\log n)\) time
• scientific article; zbMATH DE number 4062609
• Parallel multiple search

Cites work

• 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?)
• An algorithmic and complexity analysis of interpolation search
• Design and implementation of an efficient priority queue
• 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

Cited in

(5)

• Effect of data organization in a system of interleaved memories on the performance of parallel search
• Coefficients of speedup and parallel effectiveness of the parallel searching method
• Interpolation-binary search
• A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time
• 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)