2008.11.10 | Else Magård

Title: Online Sorted Range Reporting

Speaker: Mark Greve, Aarhus University, MADALGO

Abstract:
We study the following extension of the static one-dimensional range reporting problem. For an array A of n elements, build a data structure that supports the query: Given two indices i=j and an integer k, report the k smallest elements in the sub array A[i..j] in sorted order. We present a static data structure that uses O(n) words of space, supports queries in O(k) time, and can be constructed in O(n log n) time on the RAM model. We also extend the data structureto solve the online version of the problem where the elements in A[i..j] are reported in sorted order one-by-one, each element being reported in O(1) worst-case time. The datastructure has applications to e.g. top-k queries in databases, prioritized suffix tree reporting, and three-sided planar sorted range reporting.

Joint work with Brodal, Fagerberg and López-Ortiz.

Host: Gerth Stølting Brodal