Document Open Access Logo

Extensions of Self-Improving Sorters

Authors Siu-Wing Cheng , Lie Yan

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.63.pdf
  • Filesize: 422 kB
  • 12 pages

Document Identifiers

Author Details

Siu-Wing Cheng
  • HKUST, Hong Kong, China
Lie Yan
  • Hangzhou, China

Funding

  • Cheng, Siu-Wing: Supported by Research Grants Council, Hong Kong, China (project no. 16200317).
  • Yan, Lie: Part of the work was conducted while the author was at HKUST and supported by the Hong Kong PhD Fellowship.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.63

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • sorting
  • self-improving algorithms
  • entropy

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Ailon, B. Chazelle, K.L. Clarkson, D. Liu, W. Mulzer, and C. Seshadhir. Self-improving algorithms. SIAM Journal on Computing, 40(2):350-375, 2011. Google Scholar
  2. K.L. Clarkson, W. Mulzer, and C. Seshadhri. Self-improving algorithms for coordinatewise maxima and convex hulls. SIAM Journal on Computing, 43(2):617-653, 2014. Google Scholar
  3. T.M. Cover and J.A. Thomas. Elements of Information Theory. Wiley-Interscience, New York, 2nd edition, 2006. Google Scholar
  4. M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag Berlin Heidelberg, 3rd edition, 2008. Google Scholar
  5. J.R. Driscoll, N. Sarnak, D.D. Sleator, and R.E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38:86-124, 1989. Google Scholar
  6. M.L. Fredman. Two applications of a probabilistic search technique: sorting X+Y and building balanced search trees. In Proceedings of the 7th Symposium on Theory of Computing, pages 240-244, 1975. Google Scholar
  7. G.F. Italiano and R. Raman. Topics in Data Structures. In M.J. Atallah and M. Blanton, editors, Algorithms and Theory of Computation Handbook, pages 5:1-29. Chapman &Hall/CRC, 2nd edition, 2009. Google Scholar
  8. K. Mehlhorn. Nearly optimal binary search trees. Acta Informatica, 5:287-295, 1975. Google Scholar
  9. P. van Emde Boas and R. Kaas and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99-127, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact