Range selection and predecessor queries in data aware space and time

DOI10.1016/J.JDA.2017.01.002MaRDI QIDQ2397147zbMATH OpenOpenAlexFDO

Authors M. Oğuzhan Külekci, Sharma V. Thankachan

Publication date 29 May 2017

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2017.01.002

zbMATH Keywords

data structuresrange searchingdata compressionpredecessor search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Unit-time predecessor queries on massive data sets
• A new framework for addressing temporal range queries and some preliminary results
• Fast algorithms for a class of temporal range queries.
• Cache-oblivious iterated predecessor queries via range coalescing
• Time-space trade-offs for predecessor search
• Predecessor queries in dynamic integer sets
• Computing and Combinatorics
• Opportunistic data structures for range queries
• Space-Time Trade-Offs for Orthogonal Range Queries
• Query time versus redundancy trade-offs for range queries

Cites work

• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• Adaptive and approximate orthogonal range counting
• Compressed Prefix Sums
• Compressed data structures: Dictionaries and data-aware measures
• Data structures for path queries
• Data structures for range median queries
• Efficient Data Structures for the Orthogonal Range Successor Problem
• Efficient Storage and Retrieval by Content and Address of Static Files
• Improved algorithms for the range next value problem and applications
• New algorithms on wavelet trees and applications to information retrieval
• Practical entropy-compressed rank/select dictionary
• Quicksort
• Range predecessor and Lempel-Ziv parsing
• Range selection and median: tight cell probe lower bounds and adaptive data structures
• Sorted range reporting
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct representations of weighted trees supporting path queries
• Towards Optimal Range Medians
• Towards optimal range medians
• Wavelet trees for all

Cited in

(1)

• Predecessor queries in dynamic integer sets

Describes a project that uses

Uses Software

• Quicksort
• Find

This page was built for publication: Range selection and predecessor queries in data aware space and time

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