Aarhus University Seal

Online Sorted Range Reporting

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Gerth Stølting Brodal
  • Rolf Fagerberg, Denmark
  • Mark Greve, Denmark
  • Alejandro López-Ortis, University of Waterloo, Canada
  • Department of Computer Science

We study the following one-dimensional range reporting problem: On an arrayA of n elements, support queries that given two indices i ≤ j and an integerk report the k smallest elements in the subarray A[i..j] in sorted order. We present a data structure in the RAM model supporting such queries in optimal O(k) time. The structure uses O(n) words of space and can be constructed in O(n logn) time. The data structure can be extended to solve the online version of the problem, where the elements in A[i..j] are reported one-by-one in sorted order, in O(1) worst-case time per element. The problem is motivated by (and is a generalization of) a problem with applications in search engines: On a tree where leaves have associated rank values, report the highest ranked leaves in a given subtree. Finally, the problem studied generalizes the classic range minimum query (RMQ) problem on arrays.

Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)173-182
Number of pages10
Publication statusPublished - 2009
EventInternational Symposium on Algorithms and Computation, ISAAC - Honolulu, United States
Duration: 18 Nov 200916 Dec 2009
Conference number: 20


ConferenceInternational Symposium on Algorithms and Computation, ISAAC
CountryUnited States

Bibliographical note

Title of the vol.: Algorithms and Computation. Proceedings. / Yingfei Dong, Ding-Zhu Du and Oscar Ibarra (eds.)
ISBN: 978-3-642-10630-9

See relations at Aarhus University Citationformats

ID: 18068093