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

• Published in: Theoretical computer science 2020-04, Vol.814, p.210-222
• Main Authors: Sanyal, Biswajit, Majumder, Subhashis, Hon, Wing-Kai, Gupta, Prosenjit
• Format: Article
• Language: English
• Subjects: Metadata structure; Procurement auction; Top-k queries
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2020.01.036

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. In the second problem, we consider the top-k procurement decision problem in a multi-item auction, where the input consists of (i) a set of items, where each item is partitioned into equal number of shares, (ii) a set of suppliers, and (iii) for each supplier, her prices of selling different shares of each item; our target is to find k procurements with the least total costs. Our solution extends the novel metadata structure G of the first problem to speed up the reporting steps. For both of the above problems, we further show that the metadata structure can be generated on the fly, thereby saving a considerable amount of storage space.