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

DOI10.1016/J.TCS.2011.01.036zbMATH Open1215.68084OpenAlexW2105634337MaRDI QIDQ533896FDOQ533896

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

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

zbMATH Keywords

succinct data structurescompressed text indexing

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

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

Cited In (13)

• 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
• Simultaneous encodings for range and next/previous larger/smaller value queries
• 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)