Optimal Encodings for Range Top-$$k$$, Selection, and Min-Max

DOI10.1007/978-3-662-47672-7_48zbMath1354.68063arXiv1411.6581OpenAlexW2203699599MaRDI QIDQ3448818

Patrick K. Nicholson, Paweł Gawrychowski

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Information storage and retrieval of data (68P20)

Related Items

Optimal Encodings for Range Top-$$k$$, Selection, and Min-Max ⋮ Simultaneous encodings for range and next/previous larger/smaller value queries ⋮ Encoding two-dimensional range top-\(k\) queries ⋮ Space-efficient data structure for next/previous larger/smaller value queries ⋮ The effective entropy of next/previous larger/smaller value queries ⋮ Unnamed Item ⋮ An Encoding for Order-Preserving Matching.

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Towards optimal range medians
• Succinct data structures for flexible text retrieval systems
• Reporting points in halfspaces
• A problem of arrangements
• Array Range Queries
• Encodings for Range Selection and Top-k Queries
• Encoding range minima and range top-2 queries
• Asymptotically Optimal Encodings for Range Selection
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Optimal Encodings for Range Top-$$k$$, Selection, and Min-Max
• A unifying look at data structures
• Spaces, Trees, and Colors
• Lowest common ancestors in trees and directed acyclic graphs
• Adaptive and Approximate Orthogonal Range Counting