Range selection and predecessor queries in data aware space and time

DOI10.1016/j.jda.2017.01.002zbMath1407.68110OpenAlexW2586700818MaRDI QIDQ2397147

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 compressiondata structuresrange searchingpredecessor search

Mathematics Subject Classification ID

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

Uses Software

• Quicksort
• Find

Cites Work

• Unnamed Item
• Unnamed Item
• New algorithms on wavelet trees and applications to information retrieval
• Improved algorithms for the range next value problem and applications
• Towards optimal range medians
• Succinct representations of weighted trees supporting path queries
• Wavelet trees for all
• Compressed data structures: Dictionaries and data-aware measures
• Sorted Range Reporting
• Towards Optimal Range Medians
• Data Structures for Range Median Queries
• Efficient Storage and Retrieval by Content and Address of Static Files
• Range Predecessor and Lempel-Ziv Parsing
• Adaptive and Approximate Orthogonal Range Counting
• Data Structures for Path Queries
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Practical Entropy-Compressed Rank/Select Dictionary
• Efficient Data Structures for the Orthogonal Range Successor Problem
• Compressed Prefix Sums
• Quicksort