The complexity of parallel multisearch on coarse-grained machines

Given rn ordered segments that form a partition of some universe (e.g., a t wo-dimensional strip), the multisearch problem consists of determining, for a set of n query points in the universe, the segments they belong to. We p resent the first nontrivial parallel deterministic scheme for performing mu ltisearch on a distributed-memory machine when m = omega(n). The scheme is designed on the BSP* model of parallel computation, a variant of Valiant's BSP which rewards blockwise communication, and relies on a suitable redunda nt representation of the segments. The time needed to answer the queries is analyzed as a function of the redundancy and of the BSP* parameters. We sh ow that optimal performance can be obtained using logarithmic redundancy. W e also prove a lower bound on the communication requirements of any determi nistic multisearch scheme realized on a distributed-memory machine. The low er bound exhibits a tradeoff between the redundancy used to represent the s egments and the performance of the scheme.