John Wanamaker once famously said: “Half the money I spend on advertising is wasted; the trouble is, I don’t know which half.” Startup Adchemy thinks that’s not true, at least not as fas as Internet advertising goes. And Mayfield Fund seems to agree, to the tune of $19 million, in a funding round that also included Hellman & Friedman and existing investor August Capital. Rajeev Motwani, one of the co-authors of the PageRank paper that got Google started, sits on the company’s board.

Unlike traditional ads, online transactions leave a trail. Adchemy’s products analyze this trail to optimize online advertising campaigns. Optimization is particularly important as advertising moves from pay-per-click to pay-for-purchase.

“Most companies stop at the level of the click,” CEO Murthy Nukala told me in a phone interview, “but we look at actions.” The company is quick to point out that it’s not a web analytics firm, like Omniture, but rather an operational tool that dynamically places and tests ads to find the most effective mix.

So far, it seems to work: The company claims a two to five times improvement in ad ROI for its customers. With over $10 billion spent in the first half of 2007 on online advertising, those can be impressive yields.