Sorted range reporting

DOI10.1007/978-3-642-31155-0_24MaRDI QIDQ2904563zbMATH OpenOpenAlexFDO

Authors Yakov Nekrich, Gonzalo Navarro

Publication date 14 August 2012

Published in Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.4509

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Algorithms on strings (68W32)

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 $x$-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

• Online sorted range reporting
• Improved data structures for the orthogonal range successor problem
• Fully Dynamic Orthogonal Range Reporting on RAM
• Orthogonal range searching in linear and almost-linear space
• Orthogonal range searching on the RAM, revisited

Cited in

(37)

• Internal pattern matching queries in a text and applications
• Succinct Non-overlapping Indexing
• Generalized substring compression
• An improved algorithm for incremental DFS tree in undirected graphs
• String indexing for top-\(k\) close consecutive occurrences
• The heaviest induced ancestors problem revisited
• Array range queries
• A linear-space data structure for range-LCP queries in poly-logarithmic time
• Substring Range Reporting
• Compact binary relation representations with rich functionality
• Non-overlapping indexing in BWT-runs bounded space
• Wheeler maps
• Ranked document selection
• On hardness of several string indexing problems
• Improved and extended locating functionality on compressed suffix arrays
• Orthogonal range searching for text indexing
• Reporting and counting maximal points in a query orthogonal rectangle
• Succinct non-overlapping indexing
• Non-overlapping indexing -- cache obliviously
• Space-efficient frameworks for top-\(k\) string retrieval
• Two-dimensional range successor in optimal time and almost linear space
• On reporting the \(L_1\) metric closest pair in a query rectangle
• Position-restricted substring searching over small alphabets
• Range selection and predecessor queries in data aware space and time
• Efficient range searching for categorical and plain data
• scientific article; zbMATH DE number 7651193 (Why is no real title available?)
• Online sorted range reporting
• Closed factorization
• Gapped indexing for consecutive occurrences
• I/O-efficient data structures for non-overlapping indexing
• Fast construction of wavelet trees
• Order-preserving indexing
• The heaviest induced ancestors problem: better data structures and applications
• Linear space adaptive data structures for planar range reporting
• Sublinear-time reductions for big data computing
• Sublinear-time reductions for big data computing
• Top-\(k\) term-proximity in succinct 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)