The deterministic complexity of parallel multisearch

Given m ordered segments that form a partition of some universe (e.g., a 2D strip), the multisearch problem consists of determining, for a set of n query points in the universe, the segments they belong to. We present the first parallel deterministic scheme that efficiently solves the problem in the case m ge n. The scheme is designed on the BSP model, a variant of Valiant's BSP that rewards blockwise communication, and uses a suitable redundant representation of the data. Both computation and communication complexities are studied as functions of the redundancy. In particular, it is shown that optimal speed-up can be achieved using logarithmic redundancy. We also prove a lower bound on the communication requirements of any multisearch scheme realized on a distributed memory machine.