IMADA - Department of Mathematics and Computer Science |
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. Host: Rolf Fagerberg SDU HOME | IMADA HOME | Previous Page Daniel Merkle |