Advertising to search engine users is a primary medium of online advertising. It is the largest source of revenue for search engines. Performance-driven advertising is essential for advertisers and search engines alike. The user response rate in search advertising refers to the observed rate of a desired user action such as click-through or conversion. To estimate the response rate, we built a near-neighbor based data extrapolation method called RespRate-LSH using locality sensitive hashing (LSH). The target response rate is estimated as the weighted average of the response rates of near neighbors identified via LSH. The hyper-parameters of RespRate-LSH were studied in detail, and its empirical performance was compared with traditional machine learning methods and with deep neural networks. RespRate-LSH showed exemplary performance.