DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click HERE
to register or log in.
Parallel Interpolation Search.
HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB
Pagination or Media Count:
This paper concerns the problem of searching, with p parallel processors, for a given key in a random ordered table of size n. We propose a parallel interpolation algorithm which we show has expected time cost or equal log1 log nlogp 01 and we prove this algorithm has optimal expected time cost within a constant additive term. Author
APPROVED FOR PUBLIC RELEASE