Efficient meta-data structure in top-k queries of combinations and multi-item procurement auctions

摘要

Top-k query processing is an important building block for ranked retrieval, with various applications. In this paper, we consider two interesting top-k retrieval problems. In the first problem, we consider the r-combinations of a set S of n real numbers. Precisely, on any input set S, any positive integers k and r, our target is to generate the k best size-r subsets of S efficiently, whose sum of elements is maximized. Our method defines a novel metadata structure G for n and r, even before S and k are known, so that we can later use G to report the top-k r-combinations efficiently when S is available.