Optimal web-scale tiering as a flow problem

Leung, Gilbert, Quadrianto, Novi, Smola, Alexander and Tsioutsiouliklis, Kostas (2011) Optimal web-scale tiering as a flow problem. Published in: Lafferty, John, Williams, Chris, Shawe-Taylor, John, Zemel, Richard and Culotta, Aron, (eds.) Proceedings of the 24th Annual Conference on Neural Information Advances In Neural Information Processing Systems; Vancouver, British Columbia, Canada; 6-9 December 2010. 1 (23) 1333-1341. Curran Associates, Red Hook, NY. ISBN 9781617823800

[img]
Preview
PDF
Download (541kB) | Preview

Abstract

We present a fast online solver for large scale parametric max-flow problems as they occur in portfolio optimization, inventory management, computer vision, and logistics. Our algorithm solves an integer linear program in an online fashion. It exploits total unimodularity of the constraint matrix and a Lagrangian relaxation to solve the problem as a convex online game. The algorithm generates approximate solutions of max-flow problems by performing stochastic gradient descent on a set of flows. We apply the algorithm to optimize tier arrangement of over 84 million web pages on a layered set of caches to serve an incoming query stream optimally.

Item Type: Conference Proceedings
Schools and Departments: School of Engineering and Informatics > Informatics
Subjects: Q Science > Q Science (General)
Depositing User: Novi Quadrianto
Date Deposited: 24 Feb 2014 14:02
Last Modified: 16 Jun 2017 15:59
URI: http://sro.sussex.ac.uk/id/eprint/47610

View download statistics for this item

📧 Request an update