On the Optimality of Top-k Algorithms for Interactive Web Applications
Yael Amsterdamer, Daniel Deutch, Tova Milo · 2011
In an interactive Web application, the application state changes according to user choices/actions. To assist users in their interaction with such applications, there is a need to provide them with recommendations for the top-k (according to some ranking metric) interactions. These recommendations must be continually updated, as the user interacts with the application, to be consistent with the actual choices she makes. Efficiency of computation is critical here to provide fast response time and a pleasant user experience. This paper establishes formal foundations for measuring the optimality of top-k algorithms of the aforementioned type, i.e. how well they perform relative to other algorithms, with respect to all possible input instances. We define several intuitive notions of optimality in this setting, analyze the fundamental difficulties in obtaining optimal algorithms, and identify conditions under which such algorithms exist. 1.