Combined data structure for previous- and next-smaller-values

DOI10.1016/J.TCS.2011.01.036MaRDI QIDQ533896zbMATH OpenOpenAlexFDO

Authors Johannes Fischer

Publication date 10 May 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.01.036

zbMATH Keywords

succinct data structurescompressed text indexing

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• The effective entropy of next/previous larger/smaller value queries
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Optimal succinctness for range minimum queries

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• A Compressed Enhanced Suffix Array Supporting Fast String Matching
• A Uniform Approach Towards Succinct Representation of Trees
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Compressed representations of sequences and full-text indexes
• Compressed suffix trees with full functionality
• Faster entropy-bounded compressed suffix trees
• Fully-Compressed Suffix Trees
• Fully-functional succinct trees
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• Optimal succinctness for range minimum queries
• Representing trees of higher degree
• Space efficient suffix trees
• Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
• Succinct Ordinal Trees Based on Tree Covering
• Succinct ordinal trees with level-ancestor queries
• Succinct representation of balanced parentheses and static trees
• Waiting patterns for a printer
• Wee LCP

Cited in

(12)

• Space efficient data structures for nearest larger neighbor
• The effective entropy of next/previous larger/smaller value queries
• Space efficient data structures for nearest larger neighbor
• Improved algorithms for the range next value problem and applications
• Space-efficient data structure for next/previous larger/smaller value queries
• Representation of ordered trees with a given degree distribution
• Encoding Nearest Larger Values
• An encoding for order-preserving matching
• Space-efficient parallel construction of succinct representations of suffix tree topologies
• Encoding nearest larger values
• Fast relative Lempel-Ziv self-index for similar sequences
• Burrows-Wheeler transform and LCP array construction in constant space

This page was built for publication: Combined data structure for previous- and next-smaller-values

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