(Logo)   IMADA
University of Southern Denmark IMADA - Department of Mathematics and Computer Science
   

COMPUTER SCIENCE COLLOQUIUM

Online Sorted Range Reporting

Mark Greve
Department of Computer Science
University of Aarhus

Wednesday, 11 March, 2009 at 14:15
Auditorium U47

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 structure to 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 data structure 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: Rolf Fagerberg


SDU HOME | IMADA HOME | Previous Page
Daniel Merkle