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
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