The generation of large-scale data sets is a fundamental requirement of systems biology. But despite recent advances, generation of such high-coverage data remains a major challenge. We developed a pooling-deconvolution strategy that can dramatically decrease the effort required. This strategy, pooling with imaginary tags followed by deconvolution (PI-deconvolution), allows the screening of 2(n) probe proteins (baits) in 2 x n pools, with n replicates for each bait. Deconvolution of baits with their binding partners (preys) can be achieved by reading the prey's profile from the 2 x n experiments. We validated this strategy for protein-protein interaction mapping using both proteome microarrays and a yeast two-hybrid array, demonstrating that PI-deconvolution can be used to identify interactions accurately with fewer experiments and better coverage. We also show that PI-deconvolution can be used to identify protein-small molecule interactions inferred from profiling the yeast deletion collection. PI-deconvolution should be applicable to a wide range of library-against-library approaches and can also be used to optimize array designs.