Shortlisting Top-K Assignments

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 wi...

Full description

Saved in:
Bibliographic Details
Main Authors: LIN, Yimin, MOURATIDIS, Kyriakos
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2013
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/1815
https://ink.library.smu.edu.sg/context/sis_research/article/2814/viewcontent/SSDBM13_aTopK.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-2814
record_format dspace
spelling sg-smu-ink.sis_research-28142016-05-03T07:17:37Z Shortlisting Top-K Assignments LIN, Yimin MOURATIDIS, Kyriakos 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. 2013-07-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/1815 info:doi/10.1145/2484838.2484859 https://ink.library.smu.edu.sg/context/sis_research/article/2814/viewcontent/SSDBM13_aTopK.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Decision makers Empirical evaluations Large datasets Ranking problems Scalable methods Specific properties Time requirements Top-k query Databases and Information Systems Numerical Analysis and Scientific Computing
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Decision makers
Empirical evaluations
Large datasets
Ranking problems
Scalable methods
Specific properties
Time requirements
Top-k query
Databases and Information Systems
Numerical Analysis and Scientific Computing
spellingShingle Decision makers
Empirical evaluations
Large datasets
Ranking problems
Scalable methods
Specific properties
Time requirements
Top-k query
Databases and Information Systems
Numerical Analysis and Scientific Computing
LIN, Yimin
MOURATIDIS, Kyriakos
Shortlisting Top-K Assignments
description 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.
format text
author LIN, Yimin
MOURATIDIS, Kyriakos
author_facet LIN, Yimin
MOURATIDIS, Kyriakos
author_sort LIN, Yimin
title Shortlisting Top-K Assignments
title_short Shortlisting Top-K Assignments
title_full Shortlisting Top-K Assignments
title_fullStr Shortlisting Top-K Assignments
title_full_unstemmed Shortlisting Top-K Assignments
title_sort shortlisting top-k assignments
publisher Institutional Knowledge at Singapore Management University
publishDate 2013
url https://ink.library.smu.edu.sg/sis_research/1815
https://ink.library.smu.edu.sg/context/sis_research/article/2814/viewcontent/SSDBM13_aTopK.pdf
_version_ 1770571595524341760