Before revision:   We empirically evaluate the proposed approach on real-world search query data and show that it outperforms existing approaches by one to two orders of magnitude in terms of its average (per element) estimation error and by 45-90\% in terms of its expected magnitude of estimation error.
After revision:  Further, we develop an efficient block coordinate descent algorithm, which, as we empirically show, produces high quality solutions, and, in a special case, we are able to solve the proposed formulation exactly in linear time using dynamic programming. We empirically evaluate the proposed approach on real-world search query data and show that it outperforms existing approaches by one to two orders of magnitude in terms of its average (per element) estimation error and by 45-90\% in terms of its expected magnitude of estimation error.