Abstract: In this paper we consider a variant of the orthogonal range reporting problem when all points should be reported in the sorted order of their -coordinates. We show that reporting two-dimensional points with this additional condition can be organized (almost) as efficiently as the standard range reporting. Moreover, our results generalize and improve the previously known results for the orthogonal range successor problem and can be used to obtain better solutions for some stringology problems.
Recommendations
Cited in
(41)- Position-restricted substring searching over small alphabets
- The heaviest induced ancestors problem: better data structures and applications
- String indexing for top-\(k\) close consecutive occurrences
- I/O-efficient data structures for non-overlapping indexing
- Reporting and counting maximal points in a query orthogonal rectangle
- Succinct non-overlapping indexing
- Ranked document selection
- On hardness of several string indexing problems
- Improved and extended locating functionality on compressed suffix arrays
- Top-k term-proximity in succinct space
- Range selection and predecessor queries in data aware space and time
- Generalized substring compression
- On reporting the \(L_1\) metric closest pair in a query rectangle
- Gapped indexing for consecutive occurrences
- Orthogonal range searching for text indexing
- Array range queries
- Succinct Non-overlapping Indexing
- Efficient range searching for categorical and plain data
- Fast construction of wavelet trees
- Order-preserving indexing
- Substring Range Reporting
- Closed factorization
- Space-efficient frameworks for top-k string retrieval
- Online sorted range reporting
- Compact binary relation representations with rich functionality
- An improved algorithm for incremental DFS tree in undirected graphs
- Non-overlapping indexing -- cache obliviously
- The heaviest induced ancestors problem revisited
- scientific article; zbMATH DE number 7651193 (Why is no real title available?)
- Sublinear-time reductions for big data computing
- A linear-space data structure for range-LCP queries in poly-logarithmic time
- Linear space adaptive data structures for planar range reporting
- Sublinear-time reductions for big data computing
- Non-overlapping indexing in BWT-runs bounded space
- Wheeler maps
- Internal pattern matching queries in a text and applications
- Maintaining the size of LZ77 on semi-dynamic strings
- Path and ancestor queries over trees with multidimensional weight vectors
- Generalized straight-line programs
- Computing MEMs and relatives on repetitive text collections
- Two-dimensional range successor in optimal time and almost linear space
This page was built for publication: Sorted range reporting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904563)
