File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Entropy-based Scheduling Policy for Cross Aggregate Ranking Workloads

TitleEntropy-based Scheduling Policy for Cross Aggregate Ranking Workloads
Authors
Issue Date2016
Citation
IEEE Transactions on Services Computing, 2016 How to Cite?
AbstractMany data exploration applications require the ability to identify the top-k results according to a scoring function. We study a class of top-k ranking problems where top-k candidates in a dataset are scored with the assistance of another set. We call this class of workloads cross aggregate ranking. Example computation problems include evaluating the Hausdorff distance between two datasets, finding the medoid or radius within one dataset, and finding the closest or farthest pair between two datasets. In this paper, we propose a parallel and distributed solution to process cross aggregate ranking workloads. Our solution subdivides the aggregate score computation of each candidate into tasks while constantly maintains the tentative top-k results as an uncertain top-k result set. The crux of our proposed approach lies in our entropy-based scheduling technique to determine result-yielding tasks based on their abilities to reduce the uncertainty of the tentative result set. Experimental results show that our proposed approach consistently outperforms the best existing one in two different types of cross aggregate rank workloads using real datasets.
Persistent Identifierhttp://hdl.handle.net/10722/232840

 

DC FieldValueLanguage
dc.contributor.authorDai, CC-
dc.contributor.authorNutanong, S-
dc.contributor.authorChow, CY-
dc.contributor.authorCheng, CK-
dc.date.accessioned2016-09-20T05:32:49Z-
dc.date.available2016-09-20T05:32:49Z-
dc.date.issued2016-
dc.identifier.citationIEEE Transactions on Services Computing, 2016-
dc.identifier.urihttp://hdl.handle.net/10722/232840-
dc.description.abstractMany data exploration applications require the ability to identify the top-k results according to a scoring function. We study a class of top-k ranking problems where top-k candidates in a dataset are scored with the assistance of another set. We call this class of workloads cross aggregate ranking. Example computation problems include evaluating the Hausdorff distance between two datasets, finding the medoid or radius within one dataset, and finding the closest or farthest pair between two datasets. In this paper, we propose a parallel and distributed solution to process cross aggregate ranking workloads. Our solution subdivides the aggregate score computation of each candidate into tasks while constantly maintains the tentative top-k results as an uncertain top-k result set. The crux of our proposed approach lies in our entropy-based scheduling technique to determine result-yielding tasks based on their abilities to reduce the uncertainty of the tentative result set. Experimental results show that our proposed approach consistently outperforms the best existing one in two different types of cross aggregate rank workloads using real datasets.-
dc.languageeng-
dc.relation.ispartofIEEE Transactions on Services Computing-
dc.titleEntropy-based Scheduling Policy for Cross Aggregate Ranking Workloads-
dc.typeArticle-
dc.identifier.emailCheng, CK: ckcheng@cs.hku.hk-
dc.identifier.authorityCheng, CK=rp00074-
dc.identifier.doi10.1109/TSC.2016.2586062-
dc.identifier.hkuros265231-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats