Internet users search the web for more and more relevant information, such as where to find the best online deals, where to go for vacation, what to wear to a wedding, and many others. Online search advertisers target these users based on their search queries. Targeting the right set of users is important as each user clicking on an online search ad costs money to the advertiser. Savvy advertisers usually pick keywords that are niche and "non-intuitive" because such keywords are cheaper than more popular keywords due to lesser number of advertisers competing for them. In order to find such keywords, multiple information sources such as web ontologies open to the public, search engine results, and search query logs were mined in the past. In these studies, the universe of all relevant keywords was approximated as the relevant keywords of all techniques combined. A given keyword selection technique was then evaluated based on the relevance of the keywords it selected to the target page that is to be advertised. Since the universe of relevant keywords was approximate, it had implications for advertising efficiency. For the campaign dataset we used in this study, out of a total of $75K spent on the campaign, 10% of this total budget was spent on the irrelevant queries. Our primary goal in this work is to reduce this excess budget spent on the irrelevant queries. For this purpose, we learn the characteristics of the "irrelevant" queries using the campaign's past performance data. Words and phrases that occur frequently in queries, which are not likely to convert, are used as a proxy to decide who not to advertise to. In this way, we plan to preserve more of the marketing budget for queries that are more likely to convert. In our empirical study, we used a logistic regressor for identifying negative words, which distinguished the non-converting queries from the converting ones, and pruned the non-converting queries using the negatives identified. Our approach decreased the average customer acquisition cost of a live search campaign by 25% and cut the overall campaign spend by 28.6%. (C) 2015 Elsevier B.V. All rights reserved.