DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2018.63

Extensions of Self-Improving Sorters

Authors: Siu-Wing Cheng and Lie Yan

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract

Ailon et al. (SICOMP 2011) proposed a self-improving sorter that tunes its performance to the unknown input distribution in a training phase. The distribution of the input numbers x_1,x_2,...,x_n must be of the product type, that is, each x_i is drawn independently from an arbitrary distribution D_i, and the D_i's are independent of each other. We study two extensions that relax this requirement. The first extension models hidden classes in the input. We consider the case that numbers in the same class are governed by linear functions of the same hidden random parameter. The second extension considers a hidden mixture of product distributions.

Cite as

Siu-Wing Cheng and Lie Yan. Extensions of Self-Improving Sorters. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 63:1-63:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.ISAAC.2018.63,
  author =	{Cheng, Siu-Wing and Yan, Lie},
  title =	{{Extensions of Self-Improving Sorters}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{63:1--63:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.63},
  URN =		{urn:nbn:de:0030-drops-100111},
  doi =		{10.4230/LIPIcs.ISAAC.2018.63},
  annote =	{Keywords: sorting, self-improving algorithms, entropy}
}

Search Results

Documents authored by Yan, Lie

Extensions of Self-Improving Sorters

Abstract

Cite as

Thanks for your feedback!

Could not send message