Space-Time Trade-Offs for Orthogonal Range Queries

DOI10.1137/0218051MaRDI QIDQ3833664zbMATH OpenOpenAlexFDO

Authors Pravin M. Vaidya

Publication date 1989

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0218051

zbMATH Keywords

lower boundsrange queriesspace-time trade-off

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Algorithms in computer science (68W99)

Recommendations

• Lower bounds for orthogonal range searching: part II. The arithmetic model
• Lower bounds for orthogonal range searching: I. The reporting case
• scientific article; zbMATH DE number 3907783
• On the difficulty of range searching
• Orthogonal range searching in linear and almost-linear space

Cited in

(20)

• The \(n\)-dimensional \(k\)-vector and its application to orthogonal range searching
• Space-time trade-offs for some ranking and searching queries
• Time complexity of multidimensional range queries in multiple storage units.
• Sparse dominance queries for many points in optimal time and space
• Orthogonal range searching on the RAM, revisited
• Space-efficient data-analysis queries on grids
• Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model
• Space-efficient data-analysis queries on grids
• A new framework for addressing temporal range queries and some preliminary results
• Faster Linear-space Orthogonal Range Searching in Arbitrary Dimensions
• Quantum data structure for range minimum query
• Range selection and predecessor queries in data aware space and time
• Compact and succinct data structures for multidimensional orthogonal range searching
• Non-orthogonal homothetic range partial-sum query on integer grids (extended abstract)
• Algorithms - ESA 2003
• Query time versus redundancy trade-offs for range queries
• Some properties of optimal cartesian product files for orthogonal range queries
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Space Efficient Data Structures for Dynamic Orthogonal Range Counting
• Cache-oblivious data structures for orthogonal range searching

This page was built for publication: Space-Time Trade-Offs for Orthogonal Range Queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3833664)