Encoding range minima and range top-2 queries

DOI10.1098/RSTA.2013.0131MaRDI QIDQ2955625zbMATH OpenOpenAlexWikidataFDO

Authors Pooya Davoodi, Rajeev Raman, S. Srinivasa Rao, Gonzalo Navarro

Publication date 13 January 2017

Published in Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1098/rsta.2013.0131

Mathematics Subject Classification ID

Data structures (68P05)

Cites work

• A uniform paradigm to succinctly encode various families of trees
• A unifying look at data structures
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct ordinal trees with level-ancestor queries
• Ultra-succinct representation of ordered trees with applications

Cited in

(9)

• The effective entropy of next/previous larger/smaller value queries
• Encoding Nearest Larger Values
• Encoding two-dimensional range top-k queries revisited
• Encoding two-dimensional range top-\(k\) queries
• A simple representation of tree covering utilizing balanced parentheses and efficient implementation of average-case optimal RMQs
• An encoding for order-preserving matching
• Encoding nearest larger values
• On succinct representations of binary trees
• Optimal encodings for range top-\(k\), selection, and min-max

This page was built for publication: Encoding range minima and range top-2 queries

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