Online Sorted Range Reporting

Gerth Stølting Brodal, Rolf Fagerberg, Mark Greve, and Alejandro López-Ortiz

In Proc. 20th Annual International Symposium on Algorithms and Computation, volume 5878 of Lecture Notes in Computer Science, pages 173-182. Springer Verlag, Berlin, 2009.

Abstract

We study the following one-dimensional range reporting problem: On an array A of n elements, support queries that given two indices ij and an integer k 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 log n) 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.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2009. All rights reserved.

Online version

isaac09online.pdf (157 Kb)

DOI

10.1007/978-3-642-10631-6_19

Links

BIBTEX entry

@incollection{isaac09online,
  author = "Gerth St{\o}lting Brodal and Rolf Fagerberg and Mark Greve and Alejandro L\'opez-Ortiz",
  booktitle = "Proc. 20th Annual International Symposium on Algorithms and Computation",
  doi = "10.1007/978-3-642-10631-6_19",
  issn = "978-3-642-10630-9",
  pages = "173-182",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Online Sorted Range Reporting",
  volume = "5878",
  year = "2009"
}