A growing proportion of digital advertising slots is purchased through real time bidding auctions, which enables advertisers to impose highly specific criteria on which devices and opportunities to target. Employing sophisticated targeting criteria reliably increases the performance of an ad campaign, however too strict criteria will limit its scale. This raises the need to estimate the number of anticipated ad impressions at a given campaign performance level, thus enabling advertisers to tune the campaign’s budget to an optimal performance-scale trade-off. In this paper, we provide a way to estimate campaign impressions given the campaign criteria. There are several challenges to this problem. First, the criteria contain logic to include and exclude combinations of audience segments, making the space of possible criteria exponentially large. Furthermore, it is difficult to validate predictions, because we wish to predict the number of impressions available without budget constraints, a situation we can rarely observe in practice. In our approach, we first treat the audience segment inclusion/exclusion criteria separately as a data compression problem, where we use MinHash “sketches” to estimate audience size. We then model the number of available impressions with a regularized linear regression in log space, using multiplier features motivated by the assumption that some components of the additional campaign criteria are conditionally independent. We construct a validation set by projecting observed RTB data (under real budget constraints) to get impression availability without budget constraints. Using this approach, our average prediction is a factor of 2.2 from the true impression availability, and the deployed product responds to user requests in well under a second, meeting both accuracy and latency requirements for decision making in the execution of advertising campaigns.