Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
From MaRDI portal
Publication:4828937
zbMath1093.68582arXiv0705.0552MaRDI QIDQ4828937
Venkatesh Raman, S. Srinivasa Rao, Rajeev Raman
Publication date: 29 November 2004
Full work available at URL: https://arxiv.org/abs/0705.0552
Related Items (75)
Optimal encodings for range majority queries ⋮ Fast construction of wavelet trees ⋮ Less space: indexing for queries with wildcards ⋮ Access, Rank, and Select in Grammar-compressed Strings ⋮ Random access to Fibonacci encoded files ⋮ GLOUDS: representing tree-like graphs ⋮ Self-indexed Text Compression Using Straight-Line Programs ⋮ Succinct posets ⋮ The myriad virtues of wavelet trees ⋮ Space-Efficient Frameworks for Top- k String Retrieval ⋮ A simple optimal representation for balanced parentheses ⋮ A space efficient direct access data structure ⋮ Grammar compressed sequences with rank/select support ⋮ Approximate string matching with compressed indexes ⋮ A simple storage scheme for strings achieving entropy bounds ⋮ Implicit \(B\)-trees: A new data structure for the dictionary problem ⋮ Compact Indexes for Flexible Top-$$k$$ Retrieval ⋮ Compact binary relation representations with rich functionality ⋮ Faster Lightweight Lempel-Ziv Parsing ⋮ Compressed indexes for text with wildcards ⋮ Colored range queries and document retrieval ⋮ On compressing and indexing repetitive sequences ⋮ Encoding 2D range maximum queries ⋮ Ultra-succinct representation of ordered trees with applications ⋮ Finding range minima in the middle: approximations and applications ⋮ New algorithms on wavelet trees and applications to information retrieval ⋮ Stronger Lempel-Ziv based compressed text indexing ⋮ A Uniform Approach Towards Succinct Representation of Trees ⋮ Sorting and ranking of self-delimiting numbers with applications to tree isomorphism ⋮ Quad-\(k\mathrm d\) trees: a general framework for \(k\mathrm d\) trees and quad trees ⋮ Compressed text indexing with wildcards ⋮ Succinct representations of permutations and functions ⋮ A uniform paradigm to succinctly encode various families of trees ⋮ Wavelet trees for all ⋮ A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs ⋮ Succinct data structures for flexible text retrieval systems ⋮ Succinct Representations of Arbitrary Graphs ⋮ Improved approximate string matching using compressed suffix data structures ⋮ Practical compressed suffix trees ⋮ High-order entropy compressed bit vectors with rank/select ⋮ siEDM: an efficient string index and search algorithm for edit distance with moves ⋮ Rank and select operations on a word ⋮ A simpler analysis of Burrows-Wheeler-based compression ⋮ Adaptive searching in succinctly encoded binary relations and tree-structured documents ⋮ Compressed data structures: Dictionaries and data-aware measures ⋮ Rank and select revisited and extended ⋮ Optimal lower bounds for rank and select indexes ⋮ Succinct indexes for reporting discriminating and generic words ⋮ Efficient dynamic range minimum query ⋮ Succincter Text Indexing with Wildcards ⋮ Self-indexing Based on LZ77 ⋮ LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations ⋮ LRM-trees: compressed indices, adaptive sorting, and compressed permutations ⋮ Combined data structure for previous- and next-smaller-values ⋮ Spaces, Trees, and Colors ⋮ Space-efficient construction of Lempel-Ziv compressed text indexes ⋮ New space/time tradeoffs for top-\(k\) document retrieval on sequences ⋮ On compact representations of all-pairs-shortest-path-distance matrices ⋮ Succinct data structures for searchable partial sums with optimal worst-case performance ⋮ Indexing and querying character sets in one- and two-dimensional words ⋮ Compressed indexes for approximate string matching ⋮ Fully Functional Static and Dynamic Succinct Trees ⋮ Dynamic rank/select structures with applications to run-length encoded texts ⋮ Rank/select on dynamic compressed sequences and applications ⋮ Dynamic path queries in linear space ⋮ Accelerated partial decoding in wavelet trees ⋮ Compact structure for sparse undirected graphs based on a clique graph partition ⋮ Faster entropy-bounded compressed suffix trees ⋮ A Space-Optimal Grammar Compression. ⋮ Rainbowfish: A Succinct Colored de Bruijn Graph Representation ⋮ Succinct Representations of Ordinal Trees ⋮ Improved and extended locating functionality on compressed suffix arrays ⋮ Bottom-\(k\) document retrieval ⋮ Succinct Color Searching in One Dimension ⋮ Succinct dynamic cardinal trees
This page was built for publication: Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
