Extensions of Self-Improving Sorters

06/20/2019

∙

by   Siu-Wing Cheng, et al.

∙

0

∙

share

Ailon et al. (SICOMP 2011) proposed a self-improving sorter that tunes its performance to an unknown input distribution in a training phase. The input numbers x_1,x_2,...,x_n come from a product distribution, that is, each x_i is drawn independently from an arbitrary distribution D_i. We study two relaxations of 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.