Sorted range reporting

DOI10.1007/978-3-642-31155-0_24zbMATH Open1347.68343arXiv1204.4509OpenAlexW1518925092MaRDI QIDQ2904563FDOQ2904563

Authors: Yakov Nekrich, Gonzalo Navarro 

Publication date: 14 August 2012

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

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.

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

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

Mathematics Subject Classification ID

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

Cited In (37)

• Title not available (Why is that?)
• Efficient range searching for categorical and plain data
• On reporting the \(L_1\) metric closest pair in a query rectangle
• A linear-space data structure for range-LCP queries in poly-logarithmic time
• On hardness of several string indexing problems
• Improved and extended locating functionality on compressed suffix arrays
• Non-overlapping indexing -- cache obliviously
• Fast construction of wavelet trees
• Order-preserving indexing
• I/O-efficient data structures for non-overlapping indexing
• An improved algorithm for incremental DFS tree in undirected graphs
• The heaviest induced ancestors problem revisited
• Array range queries
• Reporting and counting maximal points in a query orthogonal rectangle
• Online sorted range reporting
• Closed factorization
• The heaviest induced ancestors problem: better data structures and applications
• Internal pattern matching queries in a text and applications
• Compact binary relation representations with rich functionality
• Succinct non-overlapping indexing
• 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
• Linear space adaptive data structures for planar range reporting

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)