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)

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

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)