Skip to main content
Article
Shortlisting Top-K Assignments
SSDBM '13: Proceedings of the 25th International Conference on Scientific and Statistical Database Management: 29-31 July, Baltimore
  • Yimin LIN, Singapore Management University
  • Kyriakos MOURATIDIS, Singapore Management University
Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
7-2013
Abstract

In this paper we identify a novel query type, the top-K assignment query (αTop-K). Consider a set of objects and a set of suppliers, where each object must be assigned to one supplier. Assume that there is a cost associated with every object-supplier pair. If we allocate each object to the server with the smallest cost (for the specific object), the derived overall assignment will have the minimum total cost. In many scenarios, however, runner-up assignments may be required too, like for example when a decision maker needs to make additional considerations, not captured by individual object-supplier costs. In this case, it is necessary to examine several shortlisted assignments before choosing one. This motivates the αTop-K query, which computes the K best assignments, i.e., those achieving the K smallest total costs. Algorithms for the traditional assignment ranking problem could be adapted to process the query, but their time requirements are prohibitive for large datasets (cubic to the input size). In this work we exploit the specific properties of the αTop-K problem and develop scalable methods for its processing. We also consider its incremental version, where K is not specified in advance; instead, the best assignments are iteratively computed on demand. An empirical evaluation with real data verifies the practicality and efficiency of our framework.

Keywords
  • Decision makers,
  • Empirical evaluations,
  • Large datasets,
  • Ranking problems,
  • Scalable methods,
  • Specific properties,
  • Time requirements,
  • Top-k query
ISBN
9781450319218
Identifier
10.1145/2484838.2484859
Publisher
ACM
City or Country
New York
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Additional URL
http://dx.doi.org/10.1145/2484838.2484859
Citation Information
Yimin LIN and Kyriakos MOURATIDIS. "Shortlisting Top-K Assignments" SSDBM '13: Proceedings of the 25th International Conference on Scientific and Statistical Database Management: 29-31 July, Baltimore (2013)
Available at: http://works.bepress.com/kyriakos_mouratidis/40/