Multi-Target Block Partial Search

摘要

We generalize the partial search for a more general case as a database with multiple target blocks with multiple target items. We consider a case when each target block has the same number of target items. First, we present a multi-target block partial search algorithm, which finds one of the target blocks. Second, we show a universality of this algorithm for large size of the blocks. Third, we minimize the number of queries to the oracle. Finally, we design a sure success way for realistic applications.