Prague Stringology Conference 2024
Golnaz Badkobeh, Sehar Naveed and Simon J. Puglisi
On Practical Data Structures for Sorted Range Reporting
| Abstract: |
| Given an array A[1,n] of integers, the sorted range reporting problem is to preprocess A in order to later answer queries of the form sort(i, j), which should return an array of length j-i+1 that contains the contents of A[i, j] sorted in ascending order. When applied to the suffix array, sorted range reporting can be applied to solve several string processing problems, including, for example, non-overlapping pattern matching and variable-length gapped pattern matching. In this paper we explore the practical performance of solutions for sorted range reporting. Our experiments show that the choice of solution depends on the interval size. For very short intervals, manually sorting the range at query time beats asymptotically optimal methods, while for longer intervals, a data structure that we describe that precomputes sorted blocks of varying sizes which are then merged at query time is the method of choice. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |