ICS Theory Group

October 30, Fall Quarter 2009: Thoery Seminar

1:00pm in 1423 Bren Hall

Online Sorted Range Reporting

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

To appear at ISAAC '09 (International Symposium on Algorithms and Computation)

Presented by Darren StrashUC Irvine

Consider the following one-dimensional range reporting problem: given an array A of n elements, report the k smallest elements in the subarray A[i..j] in sorted order. We present a data structure in the RAM model that supports such queries in O(k) time, using O(n) words of memory, and O(n log n) preprocessing time. We also discuss how to extend this result to the online version of the problem.